A Note on the Rainbow Connection of Random Regular Graphs

  • Michael Molloy
Keywords: Random regular graphs

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.

Published
2017-09-08
Article Number
P3.49