Proof of the Alon-Yuster conjecture

János Komlós; Gábor N. Sárközy; Endre Szemerédi

doi:10.1016/S0012-365X(00)00279-X

Proof of the Alon-Yuster conjecture

János Komlós, Gábor N. Sárközy, Endre Szemerédi

School of Arts and Sciences, Mathematics

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

95 Scopus citations

Abstract

In this paper we prove the following conjecture of Alon and Yuster. Let H be a graph with h vertices and chromatic number k. There exist constants c(H) and n₀(H) such that if n ≥ n₀(H) and G is a graph with hn vertices and minimum degree at least (1 - 1/k)hn + c(H), then G contains an H-factor. In fact, we show that if H has a k-coloring with color-class sizes h₁ ≤ h₂ ≤ ⋯ ≤ h_k, then the conjecture is true with c(H)=h_k+h_k-1 - 1.

Original language	English (US)
Pages (from-to)	255-269
Number of pages	15
Journal	Discrete Mathematics
Volume	235
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(00)00279-X
State	Published - May 28 2001

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(00)00279-X

Cite this

@article{adf80e80644a4d18821e4c50c0f3027d,

title = "Proof of the Alon-Yuster conjecture",

abstract = "In this paper we prove the following conjecture of Alon and Yuster. Let H be a graph with h vertices and chromatic number k. There exist constants c(H) and n0(H) such that if n ≥ n0(H) and G is a graph with hn vertices and minimum degree at least (1 - 1/k)hn + c(H), then G contains an H-factor. In fact, we show that if H has a k-coloring with color-class sizes h1 ≤ h2 ≤ ⋯ ≤ hk, then the conjecture is true with c(H)=hk+hk-1 - 1.",

author = "J{\'a}nos Koml{\'o}s and S{\'a}rk{\"o}zy, {G{\'a}bor N.} and Endre Szemer{\'e}di",

year = "2001",

month = may,

day = "28",

doi = "10.1016/S0012-365X(00)00279-X",

language = "English (US)",

volume = "235",

pages = "255--269",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Proof of the Alon-Yuster conjecture

AU - Komlós, János

AU - Sárközy, Gábor N.

AU - Szemerédi, Endre

PY - 2001/5/28

Y1 - 2001/5/28

N2 - In this paper we prove the following conjecture of Alon and Yuster. Let H be a graph with h vertices and chromatic number k. There exist constants c(H) and n0(H) such that if n ≥ n0(H) and G is a graph with hn vertices and minimum degree at least (1 - 1/k)hn + c(H), then G contains an H-factor. In fact, we show that if H has a k-coloring with color-class sizes h1 ≤ h2 ≤ ⋯ ≤ hk, then the conjecture is true with c(H)=hk+hk-1 - 1.

AB - In this paper we prove the following conjecture of Alon and Yuster. Let H be a graph with h vertices and chromatic number k. There exist constants c(H) and n0(H) such that if n ≥ n0(H) and G is a graph with hn vertices and minimum degree at least (1 - 1/k)hn + c(H), then G contains an H-factor. In fact, we show that if H has a k-coloring with color-class sizes h1 ≤ h2 ≤ ⋯ ≤ hk, then the conjecture is true with c(H)=hk+hk-1 - 1.

UR - http://www.scopus.com/inward/record.url?scp=0035962866&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035962866&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(00)00279-X

DO - 10.1016/S0012-365X(00)00279-X

M3 - Article

AN - SCOPUS:0035962866

SN - 0012-365X

VL - 235

SP - 255

EP - 269

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Proof of the Alon-Yuster conjecture

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this