Rainbow Connection of Graphs -- A Survey
作者： Xueliang Li , Yuefang Sun
DOI:
关键词:
摘要: The concept of rainbow connection was introduced by Chartrand et al. in 2008. It is fairly interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most the results that dealt with We begin an introduction, then try organize work into five categories, including (strong) number, $k$-connectivity, $k$-rainbow index, vertex-connection algorithms computational complexity. This also contains some conjectures, open problems or questions.
arxiv.org参考文章(37)
Wilfried Imrich, Sandi Klavžar, Richard H Hammack, Product Graphs: Structure and Recognition ,(2000)
S. T. Hedetniemi, P. J. Slater, Line graphs of triangleless graphs and iterated clique graphs Graph Theory and Applications. pp. 139- 147 ,(1972) , 10.1007/BFB0067365
Gary Chartrand, Ping Zhang, Chromatic Graph Theory ,(2008)
Yair Caro, Arie Lev, Yehuda Roditty, Zsolt Tuza, Raphael Yuster, On Rainbow Connection Electronic Journal of Combinatorics. ,vol. 15, pp. 57- ,(2008) , 10.37236/781
Avrim Blum, David Karger, An Õ( n 3/14 )-coloring algorithm for 3-colorable graphs Information Processing Letters. ,vol. 61, pp. 49- 53 ,(1997) , 10.1016/S0020-0190(96)00190-1
Ehud Friedgut, Gil Kalai, Every monotone graph property has a sharp threshold Proceedings of the American Mathematical Society. ,vol. 124, pp. 2993- 3002 ,(1996) , 10.1090/S0002-9939-96-03732-X
Miklos Simonovits, Janos Komlos, Szemeredi''s Regularity Lemma and its applications in graph theory Center for Discrete Mathematics & Theoretical Computer Science. ,(1995)
Xueliang Li, Yuefang Sun, On strong rainbow connection number arXiv: Combinatorics. ,(2010)
Ronen Shaltiel, Recent Developments in Explicit Constructions of Extractors. Bulletin of The European Association for Theoretical Computer Science. ,vol. 77, pp. 67- 95 ,(2002)
Derek G. Corneil, Stephan Olariu, Lorna Stewart, Asteroidal Triple-Free Graphs SIAM Journal on Discrete Mathematics. ,vol. 10, pp. 399- 430 ,(1997) , 10.1137/S0895480193250125