An asymptotic multipartite Kühn-Osthus theorem
Martin, Ryan R.; Mycroft, Richard; and Skokan, Jozef
(2017)
An asymptotic multipartite Kühn-Osthus theorem.
SIAM Journal on Discrete Mathematics, 31 (3).
pp. 1498-1513.
ISSN 0895-4801
In this paper we prove an asymptotic multipartite version of a well-known theorem of K¨uhn and Osthus by establishing, for any graph H with chromatic number r, the asymptotic multipartite minimum degree threshold which ensures that a large r-partite graph G admits a perfect H-tiling. We also give the threshold for an H-tiling covering all but a linear number of vertices of G, in a multipartite analogue of results of Koml´os and of Shokoufandeh and Zhao.
| Item Type | Article |
|---|---|
| Keywords | tiling,Hajnal-Szemer´edi,K¨uhn-Osthus,multipartite,regularity,linear programming |
| Departments | Mathematics |
| DOI | 10.1137/16M1070621 |
| Date Deposited | 06 Jun 2017 14:42 |
| URI | https://researchonline.lse.ac.uk/id/eprint/80196 |
Explore Further
- http://www.lse.ac.uk/Mathematics/people/Jozef-Skokan.aspx (Author)
- https://arxiv.org/pdf/1604.03002 (Publisher)
- 10.1137/16M1070621 (DOI)
-
picture_as_pdf - Skoksan_An asymptotic multipartite theorem.pdf
-
subject - Published Version
Download this file
Share this file
Downloads
ORCID: https://orcid.org/0000-0003-3996-7676