A Note on the Rainbow Connection of Random Regular Graphs

[摘要] 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.

[学科分类] 离散数学和组合数学

[关键词] Random regular graphs