Abstract
After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O(m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bondy J A, Murty U S R. Graph Theory [M]. Springer, UK, 2008.
Chartrand G, Johns G L, MeKeon K A et al. Rainbow connection in graphs [J]. Mathematica Bohemica, 2008, 133(1): 85–98.
Caro Y, Lev A, Roditty Y et al. On rainbow connection[J]. Electronic Journal of Combinatorics, 2008, 15(1): R57.
Krivelevich M, Yuster R. The rainbow connection of a graph is (at most) reciprocal to its minimum degree [J]. Journal of Graph Theory, 2010, 63(3):185–191.
Li X, Shi Y, Sun Y. Rainbow connections of graphs: A survey [J]. Graphs and Combinatorics, 2013, 29(1):1–38.
Li X, Sun Y. Rainbow Connections of Graphs [M]. Springer Briefs in Mathematics. Springer, New York, USA, 2012.
Ericksen A B. A matter of security [J]. Graduating Engineer and Computer Careers, 2007: 24–28.
Chartrand G, Okamoto F, Zhang P. Rainbow trees in graphs and generalized connectivity [J]. Networks, 2010, 55(4): 360–367.
Chakraborty S, Fischer E, Matsliah A et al. Hardness and algorithms for rainbow connection [J]. Journal of Combinatorial Optimization, 2011, 21(3): 330–347.
Chandran L S, Rajendraprasad D. Rainbow coloring of spliting and threshold graphs [C]. In: 18th Annual International Conference, COCOON 2012. Sydney, Australia, 2012.
Hammer P L, Simeone B. The splittance of a graph [J]. Combinatorica, 1981,1(3):275–284.
Liu T, Hu Y. The 3-rainbow index of graph operations [J]. WSEAS Transactions on Mathematics, 2014, 13:161–170.
Liu T, Hu Y. Some upper bounds for 3-rainbow index of graphs [J]. Journal of Combinatorial Mathematics and Combinatorial Computing, accepted.
Seward H H. Information Sorting in the Application of Electronic Digital Computers to Business Operations [D]. Massachusetts Institute of Technology, Cambridge, USA, 1954.
He J, Liang H. On rainbow-k-connectivity of random graphs [J]. Information Processing Letters, 2012, 112(10): 406–410.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the National Natural Science Foundation of China(No.11001196).
Hu Yumei, born in 1977, female, Dr, associate Prof.
Rights and permissions
About this article
Cite this article
Hu, Y., Liu, T. Three-rainbow coloring of split graphs. Trans. Tianjin Univ. 21, 284–287 (2015). https://doi.org/10.1007/s12209-015-2431-y
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12209-015-2431-y