A Note on the Rainbow Connection of Random Regular Graphs

Michael Molloy

Abstract


We prove that a random 3-regular graph has rainbow connection number $O(\log n)$. This completes the remaining open case from Rainbow connection of random regular graphs, by Dudek, Frieze and Tsourakakis.


Keywords


Random regular graphs

Full Text: PDF