An asymptotic multipartite Kühn-Osthus theorem

Ryan Martin; Richard Mycroft; Jozef Skokan

doi:10.1137/16M1070621

An asymptotic multipartite Kühn-Osthus theorem

Ryan Martin, Richard Mycroft, Jozef Skokan

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

242 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	1498-1513
Number of pages	16
Journal	SIAM Journal on Discrete Mathematics
Volume	31
Issue number	3
DOIs	https://doi.org/10.1137/16M1070621
Publication status	Published - 13 Jul 2017

Keywords

tiling
Hajnal-Szemer´edi
K¨uhn-Osthus
multipartite
regularity
linear programming

Access to Document

10.1137/16M1070621Licence: None: All rights reserved

Martin_et_al_An_asymptotic_multipartite_SIAM_Journal_on_Discrete_Mathematics_2017
© 2017, Society for Industrial and Applied Mathematics
Final published version, 377 KBLicence: Other (please specify with Rights Statement)

http://epubs.siam.org/doi/10.1137/16M1070621Licence: None: All rights reserved

Embeddings in hypergraphs
Mycroft, R. (Principal Investigator)
Engineering & Physical Science Research Council
30/03/15 → 29/03/17
Project: Research Councils

Cite this

@article{22de2edc957745839c0d752b7ff488ec,

title = "An asymptotic multipartite K{\"u}hn-Osthus theorem",

abstract = "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. ",

keywords = "tiling , Hajnal-Szemer´edi , K¨uhn-Osthus , multipartite , regularity , linear programming",

author = "Ryan Martin and Richard Mycroft and Jozef Skokan",

year = "2017",

month = jul,

day = "13",

doi = "10.1137/16M1070621",

language = "English",

volume = "31",

pages = "1498--1513",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - An asymptotic multipartite Kühn-Osthus theorem

AU - Martin, Ryan

AU - Mycroft, Richard

AU - Skokan, Jozef

PY - 2017/7/13

Y1 - 2017/7/13

N2 - 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.

AB - 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.

KW - tiling

KW - Hajnal-Szemer´edi

KW - K¨uhn-Osthus

KW - multipartite

KW - regularity

KW - linear programming

U2 - 10.1137/16M1070621

DO - 10.1137/16M1070621

M3 - Article

SN - 0895-4801

VL - 31

SP - 1498

EP - 1513

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

An asymptotic multipartite Kühn-Osthus theorem

Abstract

Keywords

Access to Document

Fingerprint

Projects

Embeddings in hypergraphs

Cite this