Three-rainbow coloring of split graphs

Yumei Hu; Tingting Liu

doi:10.1007/s12209-015-2431-y

Transactions of Tianjin University ›› 2015, Vol. 21 ›› Issue (3) : 284 -287. DOI: 10.1007/s12209-015-2431-y

Article

Three-rainbow coloring of split graphs

Yumei Hu ¹^,^a
, Tingting Liu ¹

Author information +

History +

PDF

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.

Keywords

edge coloring / 3-rainbow coloring / algorithm / split graph

Cite this article

Download citation ▾

Yumei Hu, Tingting Liu. Three-rainbow coloring of split graphs. Transactions of Tianjin University, 2015, 21(3): 284-287 DOI:10.1007/s12209-015-2431-y

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Bondy J A, Murty U S R. Graph Theory [M], 2008, UK: Springer

[2]	Chartrand G, Johns G L, MeKeon K A, et al. Rainbow connection in graphs [J]. Mathematica Bohemica, 2008, 133(1): 85-98.

[3]	Caro Y, Lev A, Roditty Y, et al. On rainbow connection[J]. Electronic Journal of Combinatorics, 2008, 15(1): R57.

[4]	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.

[5]	Li X, Shi Y, Sun Y. Rainbow connections of graphs: A survey [J]. Graphs and Combinatorics, 2013, 29(1): 1-38.

[6]	Li X, Sun Y. Rainbow Connections of Graphs [M], 2012, New York, USA: Springer

[7]	Ericksen A B. A matter of security [J]. Graduating Engineer and Computer Careers, 2007, 24-28.

[8]	Chartrand G, Okamoto F, Zhang P. Rainbow trees in graphs and generalized connectivity [J]. Networks, 2010, 55(4): 360-367.

[9]	Chakraborty S, Fischer E, Matsliah A, et al. Hardness and algorithms for rainbow connection [J]. Journal of Combinatorial Optimization, 2011, 21(3): 330-347.

[10]	Chandran L S, Rajendraprasad D. Rainbow coloring of spliting and threshold graphs [C]. In: 18th Annual International Conference, COCOON 2012. Sydney, Australia, 2012.

[11]	Hammer P L, Simeone B. The splittance of a graph [J]. Combinatorica, 1981, 1(3): 275-284.

[12]	Liu T, Hu Y. The 3-rainbow index of graph operations [J]. WSEAS Transactions on Mathematics, 2014, 13: 161-170.

[13]	Liu T, Hu Y. Some upper bounds for 3-rainbow index of graphs [J]. Journal of Combinatorial Mathematics and Combinatorial Computing, accepted.

[14]	Seward H H. Information Sorting in the Application of Electronic Digital Computers to Business Operations [D], 1954, Cambridge, USA: Massachusetts Institute of Technology.