Proof of the 1-factorization and Hamilton Decomposition Conjectures

DOI10.1090/memo/1154zbMath1367.05165OpenAlexW1493850023MaRDI QIDQ5283773

Daniela Kühn, Deryk Osthus, Andrew Treglown, Béla Csaba, Allan Lo

Publication date: 25 July 2017

Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: http://pure-oai.bham.ac.uk/ws/files/23746247/1401.4159v2

zbMATH Keywords

1-factorizationHamilton cycleHamilton decomposition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items (30)

The chromatic index of graphs with large even order \(n\) and minimum degree at least \(2n/3\) ⋮ Counting and packing Hamilton cycles in dense graphs and oriented graphs ⋮ Chromatic index of dense quasirandom graphs ⋮ A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs ⋮ A greedy algorithm for the social golfer and the Oberwolfach problem ⋮ The number of Hamiltonian decompositions of regular graphs ⋮ Independence number and the normalized Laplacian eigenvalue one ⋮ Decomposing tournaments into paths ⋮ Edge coloring graphs with large minimum degree ⋮ Optimal patrolling strategies for trees and complete networks ⋮ Maximally edge‐connected realizations and Kundu's k $k$‐factor theorem ⋮ Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs ⋮ Graph and hypergraph packing ⋮ Properties, proved and conjectured, of Keller, Mycielski, and queen graphs ⋮ Tree decompositions of graphs without large bipartite holes ⋮ A Rainbow Dirac's Theorem ⋮ Number of 1-factorizations of regular high-degree graphs ⋮ Minimum degree conditions for monochromatic cycle partitioning ⋮ A blow-up lemma for approximate decompositions ⋮ Graph edge coloring: a survey ⋮ Packing, counting and covering Hamilton cycles in random directed graphs ⋮ Compatible Hamilton cycles in Dirac graphs ⋮ Resolution of the Oberwolfach problem ⋮ Path and cycle decompositions of dense graphs ⋮ The chromatic index of strongly regular graphs ⋮ An approximate version of Jackson’s conjecture ⋮ Packing degenerate graphs ⋮ Decomposing hypergraphs into cycle factors ⋮ Decomposition of 4k-regular graphs into k 4-regular K5-free and (K5 − e)-free subgraphs ⋮ The Overfullness of Graphs with Small Minimum Degree and Large Maximum Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Edge-disjoint Hamilton cycles in graphs
• Hamiltonian degree sequences in digraphs
• Minimum degree of a graph and the existence of k-factors
• 1-factorizing regular graphs of high degree - an improved bound
• On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
• Edge coloring regular graphs of high degree
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Approximate Hamilton Decompositions of Robustly Expanding Regular Digraphs
• The robust component structure of dense regular graphs and applications
• Hamilton decompositions of regular tournaments
• The NP-Completeness of Edge-Coloring
• Edge-Disjoint Hamilton Cycles in Regular Graphs of Large Degree
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Optimal Packings of Hamilton Cycles in Sparse Random Graphs
• An Asymptotic Version of the Multigraph 1‐Factorization Conjecture
• Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree
• Regular Graphs of High Degree are 1-Factorizable
• Edge-disjoint Hamilton cycles in random graphs
• All regular multigraphs of even order and high degree are 1-factorable
• Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs

This page was built for publication: Proof of the 1-factorization and Hamilton Decomposition Conjectures