Rainbow Hamilton cycles in random regular graphs

DOI10.1002/RSA.20146MaRDI QIDQ3419610zbMATH OpenOpenAlexFDO

Authors Svante Janson, Nicholas Wormald

Publication date 7 February 2007

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

colorsprobability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A rainbow subgraph of an edge-coloured graph has all edges of distinct colours. A random d-regular graph with d even, and having edges coloured randomly with d/2 of each of n colours, has a rainbow Hamilton cycle with probability tending to 1 as n tends to infinity, provided d is at least 8.

Recommendations

• Rainbow Hamilton cycles in random graphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• On rainbow Hamilton cycles in random hypergraphs
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Rainbow matchings and Hamilton cycles in random graphs
• Colorful Hamilton Cycles in Random Graphs
• Rainbow Hamilton cycles in uniform hypergraphs
• Hamiltonian cycles in random regular graphs
• Rainbow perfect matchings and Hamilton cycles in the random geometric graph
• Rainbow Hamiltonian cycles in strongly edge-colored graphs

Cites work

• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs

Cited in

(20)

• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• From one to many rainbow Hamiltonian cycles
• The threshold for the full perfect matching color profile in a random coloring of random graphs
• Rainbow Hamilton cycles and lopsidependency
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• Rainbow matchings and Hamilton cycles in random graphs
• Rainbow arborescence in random digraphs
• Elegantly colored paths and cycles in edge colored random graphs
• Subgraphs of random k-edge-coloured k-regular graphs
• Longest partial transversals in plexes
• Rainbow perfect matchings and Hamilton cycles in the random geometric graph
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Rainbow perfect matchings in complete bipartite graphs: existence and counting
• Rainbow Hamilton cycles in random graphs
• Colorful Hamilton Cycles in Random Graphs
• Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\)
• Rainbow Hamilton Cycles in Random Geometric Graphs
• Modulo k-orientations of random regular graphs
• The emergence of a giant rainbow component
• Rainbow tetrahedra in Cayley graphs

This page was built for publication: Rainbow Hamilton cycles in random regular graphs

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