Optimal path and cycle decompositions of dense quasirandom graphs

详细信息    查看全文

• 作者：Stefan Glock¹ ; ^{sxg426@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Daniela Kü ; hn ^{d.kuhn@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Deryk Osthus ^{d.osthus@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：cycle decomposition ; path decomposition ; linear arboricity ; overfull subgraph conjecture
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：49
• 期：Complete
• 页码：65-72
• 全文大小：186 K

文摘

Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let e951d835597cb5d956810655" title="Click to view the MathML source">0<p<1$0<p<1$ be constant and let G∼G_n,p$G\sim 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$\mathit{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 ‘quasi-random’ 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.