Back to Search
Start Over
Optimal path and cycle decompositions of dense quasirandom graphs.
- Source :
-
Journal of Combinatorial Theory - Series B . May2016, Vol. 118, p88-108. 21p. - Publication Year :
- 2016
-
Abstract
- Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let 0 < p < 1 be constant and let G ∼ G n , p . Let odd ( G ) be the number of odd degree vertices in G . Then a.a.s. the following hold: (i) G can be decomposed into ⌊ Δ ( G ) / 2 ⌋ cycles and a matching of size odd ( G ) / 2 . (ii) G can be decomposed into max { odd ( G ) / 2 , ⌈ Δ ( G ) / 2 ⌉ } paths. (iii) G can be decomposed into ⌈ Δ ( G ) / 2 ⌉ linear forests. Each of these bounds is best possible. We actually derive (i)–(iii) from ‘quasirandom’ versions of our results. In that context, we also determine the edge chromatic number of a given dense quasirandom graph of even order. For all these results, our main tool is a result on Hamilton decompositions of robust expanders by Kühn and Osthus. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 118
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 113668343
- Full Text :
- https://doi.org/10.1016/j.jctb.2016.01.004