Rainbow Connection of Random Regular Graphs

DOI10.1137/140998433zbMath1325.05148arXiv1311.2299OpenAlexW1759514461WikidataQ57401413 ScholiaQ57401413MaRDI QIDQ3452164

Charalampos E. Tsourakakis, Andrzej Dudek, Alan M. Frieze

Publication date: 18 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

edge coloringrandom regular graphsrainbow connection

Mathematics Subject Classification ID

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

Related Items (13)

Joint Alignment from Pairwise Differences with a Noisy Oracle ⋮ Colorful Hamilton Cycles in Random Graphs ⋮ Rainbow connections for outerplanar graphs with diameter 2 and 3 ⋮ Elegantly Colored Paths and Cycles in Edge Colored Random Graphs ⋮ A note on the rainbow connection of random regular graphs ⋮ Rainbow connectivity and rainbow index of inhomogeneous random graphs ⋮ Concentration of rainbow \(k\)-connectivity of a multiplex random graph ⋮ The threshold for the full perfect matching color profile in a random coloring of random graphs ⋮ Rainbow \(k\)-connectivity of random bipartite graphs ⋮ On the threshold for rainbow connection number \(r\) in random graphs ⋮ Rainbow and monochromatic vertex-connection of random graphs ⋮ Pattern Colored Hamilton Cycles in Random Graphs ⋮ Rainbow connectivity and rainbow criticality on graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some remarks on rainbow connectivity
• Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
• On rainbow-\(k\)-connectivity of random graphs
• Hardness and algorithms for rainbow connection
• Rainbow connection number and radius
• On rainbow connection
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Sandwiching random graphs: universality between random graph models
• Rainbow connections of graphs: a survey
• The hitting time of rainbow connection number two
• Rainbow connection number and connected dominating sets
• Rainbow Connectivity of Sparse Random Graphs
• Rainbow connection in graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

This page was built for publication: Rainbow Connection of Random Regular Graphs