Almost all optimally coloured complete graphs contain a rainbow Hamilton path
From MaRDI portal
Abstract: A subgraph of an edge-coloured graph is called rainbow if all of the edges of have different colours. In 1989, Andersen conjectured that every proper edge-colouring of admits a rainbow path of length . We show that almost all optimal edge-colourings of admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.
Recommendations
- Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
- On rainbow cycles in edge colored complete graphs
- Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
- Rainbow Hamilton cycles in random graphs and hypergraphs
- Rainbow Hamilton cycles in random regular graphs
Cites work
- A counterexample to Stein's equi-\(n\)-square conjecture
- A lower bound for the length of a partial transversal in a Latin square
- Almost all Steiner triple systems are almost resolvable
- Almost all Steiner triple systems have perfect matchings
- An n n Latin square has a transversal with at least n- n distinct symbols
- An upper bound on the number of Steiner triple systems
- Asymptotic behavior of the chromatic index for hypergraphs
- Combinatorial matrix theory
- Counting designs
- Decompositions into isomorphic rainbow spanning trees
- Decompositions into spanning rainbow structures
- Edge-Disjoint Isomorphic Multicolored Trees and Cycles in Complete Graphs
- Hamilton circuits with many colours in properly edge-coloured complete graphs.
- scientific article; zbMATH DE number 3613053 (Why is no real title available?)
- Intercalates and discrepancy in random Latin squares
- Linearly many rainbow trees in properly edge-coloured complete graphs
- Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
- Long rainbow cycles in proper edge-colorings of complete graphs
- Most Latin squares have many subsquares
- Multicolored trees in complete graphs
- Number of 1-factorizations of regular high-degree graphs
- On a hypergraph matching problem
- On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
- On rainbow cycles in edge colored complete graphs
- Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
- Rainbow and orthogonal paths in factorizations of K_n
- Rainbow structures in locally bounded colorings of graphs
- Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
- Spanning trees in random graphs
- The maximum number of perfect matchings in graphs with a given degree sequence
- Transversals of latin squares and their generalizations
Cited in
(7)- Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
- Transversal Hamilton cycle in hypergraph systems
- Rainbow subgraphs of uniformly coloured randomly perturbed graphs
- Rainbow Hamiltonicity in uniformly coloured perturbed digraphs
- The polychromatic domination number
- Rainbow spanning trees in uniformly coloured perturbed graphs (extended abstract)
- Transversal Hamilton cycle in the hypergraph system
This page was built for publication: Almost all optimally coloured complete graphs contain a rainbow Hamilton path
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2673480)
