Rainbow connection of random regular graphs

DOI10.1137/140998433MaRDI QIDQ3452164zbMATH OpenOpenAlexWikidataFDO

Authors Andrzej Dudek, Charalampos E. Tsourakakis, Alan 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 coloringrainbow connectionrandom regular graphs

Mathematics Subject Classification ID

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

Abstract: An edge colored graph $G$ is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this work we study the rainbow connection of the random $r$-regular graph $G=G(n,r)$ of order $n$, where $rge4$ is a constant. We prove that with probability tending to one as $n$ goes to infinity the rainbow connection of $G$ satisfies $rc(G)=O(logn)$, which is best possible up to a hidden constant.

Recommendations

• Rainbow connection of sparse random graphs
• Rainbow connectivity of sparse random graphs
• Sharp concentration of the rainbow connection of random graphs
• On rainbow connection

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
• Hardness and algorithms for rainbow connection
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• On rainbow connection
• On rainbow-k-connectivity of random graphs
• Rainbow connection in graphs
• Rainbow connection number and connected dominating sets
• Rainbow connection number and radius
• Rainbow connectivity of sparse random graphs
• Random graphs.
• Sandwiching random graphs: universality between random graph models
• The hitting time of rainbow connection number two
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

Cited in

(17)

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

This page was built for publication: Rainbow connection of random regular graphs

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