Optimal path and cycle decompositions of dense quasirandom graphs

DOI10.1016/J.JCTB.2016.01.004zbMATH Open1332.05078arXiv1503.00494OpenAlexW1532129519MaRDI QIDQ5890517FDOQ5890517

Stefan Glock, Deryk Osthus, Daniela Kühn

Publication date: 14 March 2016

Published in: Electronic Notes in Discrete Mathematics, Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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 $Gsim{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 $lfloorDelta(G)/2floor$ cycles and a matching of size $odd(G)/2$. (ii) $G$ can be decomposed into $maxodd(G)/2,lceilDelta(G)/2ceil$ paths. (iii) $G$ can be decomposed into $lceilDelta(G)/2ceil$ 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"uhn and Osthus.

Full work available at URL: https://arxiv.org/abs/1503.00494

zbMATH Keywords

path decompositioncycle decompositionlinear arboricityquasirandom graphrobust expanderoverfull subgraph conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graphs.
• The NP-Completeness of Edge-Coloring
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• A constructive proof of Vizing's theorem
• How to find overfull subgraphs in graphs with large maximum degree
• Hamiltonian degree sequences in digraphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Edge-disjoint Hamilton cycles in random graphs
• Cycle packing
• Regular Graphs of High Degree are 1-Factorizable
• The linear arboricity of graphs
• Linear arboricity of random regular graphs
• Optimal Packings of Hamilton Cycles in Sparse Random Graphs
• The Representation of a Graph by Set Intersections
• Optimal covers with Hamilton cycles in random graphs
• Proof of the $1$-factorization and Hamilton Decomposition Conjectures
• Arboricity and spanning-tree packing in random graphs with an application to load balancing
• Gallai's conjecture for disconnected graphs
• Overfull conjecture for graphs with high minimum degree
• Decomposing Random Graphs into Few Cycles and Edges

Cited In (17)

• A decomposition method on solving the linear arboricity conjecture
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• The conjunction of the linear arboricity conjecture and Lovász's path partition theorem
• A blow-up lemma for approximate decompositions
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Towards the Erdős-Gallai cycle decomposition conjecture
• Long path and cycle decompositions of even hypercubes
• Towards the linear arboricity conjecture
• Optimal packings of bounded degree trees
• Graph and hypergraph colouring via nibble methods: a survey
• Chromatic index of dense quasirandom graphs
• Linear arboricity of degenerate graphs
• A proof of the Erdős-Faber-Lovász conjecture
• Towards the Erdős-Gallai cycle decomposition conjecture
• Edge coloring graphs with large minimum degree
• Path and cycle decompositions of dense graphs
• On computing the path number of a graph

This page was built for publication: Optimal path and cycle decompositions of dense quasirandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890517)