Some remarks on rainbow connectivity

DOI10.1016/j.endm.2015.06.019zbMath1346.05074arXiv1501.00821OpenAlexW2596788260MaRDI QIDQ322204

Nina Kamčev, Michael Krivelevich, Benjamin Sudakov

Publication date: 14 October 2016

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

diameterrandom regular graphsrainbow connectivityrandom regular graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Connectivity (05C40)

Related Items (11)

Colorful Hamilton Cycles in Random Graphs ⋮ Upper bounding rainbow connection number by forest number ⋮ Rainbow Connection of Random Regular Graphs ⋮ Conflict-free connections of 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 ⋮ Conflict-free connection number and independence number of a graph ⋮ Rainbow \(k\)-connectivity of random bipartite graphs ⋮ Pattern Colored Hamilton Cycles in Random Graphs

Cites Work

• Unnamed Item
• Hardness and algorithms for rainbow connection
• Rainbow connection number and radius
• On rainbow connection
• The isoperimetric number of random regular graphs
• Radius, diameter, and minimum degree
• The diameter of random regular graphs
• Rainbow connections of graphs: a survey
• Rainbow connection number and connected dominating sets
• Smoothed Analysis on Connected Graphs
• Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs
• Rainbow Connectivity of Sparse Random Graphs
• Rainbow connection in graphs
• The Diameter of a Cycle Plus a Random Matching
• Almost all regular graphs are hamiltonian
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Splitting an Expander Graph
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

This page was built for publication: Some remarks on rainbow connectivity