Abstract | ||
---|---|---|
In this paper we prove the following conjecture by Bollobás and Komlós: For every γ>0 and positive integers r and Δ, there exists β>0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least (r−1r+γ)n and H is an r-chromatic graph with n vertices, bandwidth at most βn and maximum degree at most Δ, then G contains a copy of H. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1016/j.endm.2007.07.075 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
extremal graph theory,spanning subgraphs,regularity lemma | Wheel graph,Discrete mathematics,Combinatorics,Bound graph,Graph power,Quartic graph,Cycle graph,Graph bandwidth,Degree (graph theory),Mathematics,Path graph | Journal |
Volume | ISSN | Citations |
29 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Julia Böttcher | 1 | 93 | 17.35 |
Mathias Schacht | 2 | 361 | 37.90 |
Anusch Taraz | 3 | 168 | 37.71 |