Optimal path and cycle decompositions of dense quasirandom graphs

DOI10.1016/j.jctb.2016.01.004zbMath1332.05078arXiv1503.00494OpenAlexW1532129519MaRDI QIDQ5890517

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)

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

zbMATH Keywords

linear arboricitypath decompositioncycle decompositionoverfull subgraph conjecturequasirandom graphrobust expander

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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