H-factors in dense graphs

Noga Alon; Raphael Yuster

doi:10.1006/jctb.1996.0020

H-factors in dense graphs

Noga Alon, Raphael Yuster

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

112 Scopus citations

Abstract

The following asymptotic result is proved. For every ε > 0, and for every positive integer h, there exists an n₀ = n₀(ε, h) such that for every graph H with h vertices and for every n>n₀, any graph G with hn vertices and with minimum degree d≥((x(H) - 1)/x(H) +ε) hn contains n vertex disjoint copies of H. This result is asymptotically tight and its proof supplies a polynomial time algorithm for the corresponding algorithmic problem.

Original language	English (US)
Pages (from-to)	269-282
Number of pages	14
Journal	Journal of Combinatorial Theory. Series B
Volume	66
Issue number	2
DOIs	https://doi.org/10.1006/jctb.1996.0020
State	Published - Mar 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1996.0020

Cite this

@article{669a0bbfa94e46a087c8fe25ba11ba3e,

title = "H-factors in dense graphs",

abstract = "The following asymptotic result is proved. For every ε > 0, and for every positive integer h, there exists an n0 = n0(ε, h) such that for every graph H with h vertices and for every n>n0, any graph G with hn vertices and with minimum degree d≥((x(H) - 1)/x(H) +ε) hn contains n vertex disjoint copies of H. This result is asymptotically tight and its proof supplies a polynomial time algorithm for the corresponding algorithmic problem.",

author = "Noga Alon and Raphael Yuster",

note = "Funding Information: * Research supported in part by the Fund for Basic Research administered by the Israel Academy of Sciences.",

year = "1996",

month = mar,

doi = "10.1006/jctb.1996.0020",

language = "English (US)",

volume = "66",

pages = "269--282",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - H-factors in dense graphs

AU - Alon, Noga

AU - Yuster, Raphael

N1 - Funding Information: * Research supported in part by the Fund for Basic Research administered by the Israel Academy of Sciences.

PY - 1996/3

Y1 - 1996/3

N2 - The following asymptotic result is proved. For every ε > 0, and for every positive integer h, there exists an n0 = n0(ε, h) such that for every graph H with h vertices and for every n>n0, any graph G with hn vertices and with minimum degree d≥((x(H) - 1)/x(H) +ε) hn contains n vertex disjoint copies of H. This result is asymptotically tight and its proof supplies a polynomial time algorithm for the corresponding algorithmic problem.

AB - The following asymptotic result is proved. For every ε > 0, and for every positive integer h, there exists an n0 = n0(ε, h) such that for every graph H with h vertices and for every n>n0, any graph G with hn vertices and with minimum degree d≥((x(H) - 1)/x(H) +ε) hn contains n vertex disjoint copies of H. This result is asymptotically tight and its proof supplies a polynomial time algorithm for the corresponding algorithmic problem.

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

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

U2 - 10.1006/jctb.1996.0020

DO - 10.1006/jctb.1996.0020

M3 - Article

AN - SCOPUS:0030102833

SN - 0095-8956

VL - 66

SP - 269

EP - 282

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

H-factors in dense graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this