Abstract | ||
---|---|---|
A conjecture by Bollobas and Komlos states the following: For every@c0and integersr=2and @D, there exists@b0with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least(r-1r+@c)nand H is an r-chromatic graph with n vertices, bandwidth at most @bn and maximum degree at most @D, then G contains a copy of H. This conjecture generalises several results concerning sufficient degree conditions for the containment of spanning subgraphs. We prove the conjecture for the case r=3. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.jctb.2007.11.005 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
maximum degree,n vertex,small bandwidth,following property,3-colourable subgraphs,c0and integersr,regularity lemma,spanning subgraphs,nand h,minimum degree,large graph,r-chromatic graph,dense graph,extremal graph theory,komlos state,sufficient degree condition,bandwidth | Discrete mathematics,Combinatorics,Minimum degree spanning tree,Vertex (geometry),Bandwidth (signal processing),Degree (graph theory),Frequency partition of a graph,Extremal graph theory,Conjecture,Mathematics,Path graph | Journal |
Volume | Issue | ISSN |
98 | 4 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
5 | 0.53 | 21 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Julia Böttcher | 1 | 93 | 17.35 |
Mathias Schacht | 2 | 361 | 37.90 |
Anusch Taraz | 3 | 168 | 37.71 |