A Note on the Rainbow Connection of Random Regular Graphs

  • Michael Molloy
DOI: https://doi.org/10.37236/6789
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
How to Cite
Molloy, M. (2017). A Note on the Rainbow Connection of Random Regular Graphs. The Electronic Journal of Combinatorics, 24(3), #P3.49. https://doi.org/10.37236/6789
Issue
Volume 24, Issue 3 (2017)
Article Number
P3.49