Spanning 3-colourable subgraphs of small bandwidth in dense graphs
Böttcher, Julia
; Schacht, Mathias; and Taraz, Anusch
(2008)
Spanning 3-colourable subgraphs of small bandwidth in dense graphs
Journal of Combinatorial Theory, Series B, 98 (4).
pp. 752-777.
ISSN 0095-8956
A conjecture by Bollobás and Komlós states the following: For every γ>0 and integers r⩾2 and Δ, there exists β>0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r-1)/r+γ)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.
| Item Type | Article |
|---|---|
| Departments | Mathematics |
| DOI | 10.1016/j.jctb.2007.11.005 |
| Date Deposited | 28 May 2012 15:44 |
| URI | https://researchonline.lse.ac.uk/id/eprint/44113 |
Explore Further
- http://www.journals.elsevier.com/journal-of-combin... (Official URL)
ORCID: https://orcid.org/0000-0002-4104-3635