# Hardness Results for Total Rainbow Connection of Graphs

Lily Chen; Bofeng Huo; Yingbin Ma

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 2, page 355-362
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topLily Chen, Bofeng Huo, and Yingbin Ma. "Hardness Results for Total Rainbow Connection of Graphs." Discussiones Mathematicae Graph Theory 36.2 (2016): 355-362. <http://eudml.org/doc/277121>.

@article{LilyChen2016,

abstract = {A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring of a graph G makes it total rainbow connected is NP-Complete. We also prove that given a graph G, deciding whether trc(G) = 3 is NP-Complete.},

author = {Lily Chen, Bofeng Huo, Yingbin Ma},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {total rainbow connection; computational complexity},

language = {eng},

number = {2},

pages = {355-362},

title = {Hardness Results for Total Rainbow Connection of Graphs},

url = {http://eudml.org/doc/277121},

volume = {36},

year = {2016},

}

TY - JOUR

AU - Lily Chen

AU - Bofeng Huo

AU - Yingbin Ma

TI - Hardness Results for Total Rainbow Connection of Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2016

VL - 36

IS - 2

SP - 355

EP - 362

AB - A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring of a graph G makes it total rainbow connected is NP-Complete. We also prove that given a graph G, deciding whether trc(G) = 3 is NP-Complete.

LA - eng

KW - total rainbow connection; computational complexity

UR - http://eudml.org/doc/277121

ER -

## References

top- [1] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008).
- [2] Y. Caro, A. Lev, Y. Roditty, Zs. Tuza and R. Yuster, On rainbow connection, Electron J. Combin. 15 (2008) R57. Zbl1181.05037
- [3] S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connectivity, J. Comb. Optim. 21 (2011) 330-347. doi:10.1007/s10878-009-9250-9[Crossref] Zbl1319.05049
- [4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
- [5] L. Chen, X. Li and Y. Shi, The complexity of determining the rainbow vertex- connection of graphs, Theoret. Comput. Sci. 412 (2011) 4531-4535. doi:10.1016/j.tcs.2011.04.032[Crossref] Zbl1223.68079
- [6] M. Garey, D.S. Johnson and L.J. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci. 1 (1976) 237-267. doi:10.1016/0304-3975(76)90059-1[Crossref] Zbl0338.05120
- [7] X. Huang, X. Li and Y. Shi, Note on the hardness of rainbow connections for planar and line graphs, Bull. Malays. Math. Sci. Soc. 88 (2015) 1235-1241. doi:10.1007/s40840-014-0077-x[WoS][Crossref] Zbl1317.05058
- [8] X. Huang, X. Li, Y. Shi, J. Yue and Y. Zhao, Rainbow connections for outerplanar graphs with diameter 2 and 3, Appl. Math. Comput. 242 (2014) 277-280. doi:10.1016/j.amc.2014.05.066[WoS][Crossref] Zbl1334.05038
- [9] M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) re- ciprocal to its minimum degree, J. Graph Theory 63 (2010) 185-191.[WoS] Zbl1193.05079
- [10] S. Li, X. Li and Y. Shi, Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs, Appl. Math. Comput. 258 (2015) 155-161. doi:10.1016/j.amc.2015.02.015[WoS][Crossref]
- [11] X. Li, Y. Mao and Y. Shi, The strong rainbow vertex-connection of graphs, Util. Math. 93 (2014) 213-223. Zbl1293.05115
- [12] X. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory 33 (2013) 307-313. doi:10.7151/dmgt.1664[WoS][Crossref]
- [13] X. Li and Y. Shi, Rainbow connection in 3-connected graphs, Graphs Combin. 29 (2013) 1471-1475. doi:10.1007/s00373-012-1204-9[WoS][Crossref] Zbl1272.05053
- [14] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1-38. doi:10.1007/s00373-012-1243-2[WoS][Crossref] Zbl1258.05058
- [15] X. Li and Y. Sun, Rainbow Connections of Graphs (New York, Springer Briefs in Math., Springer, 2012). Zbl1250.05066
- [16] H. Liu, A. Mestre and T. Sousa, Total rainbow k-connection in graphs, Discrete Appl. Math. 174 (2014) 92-101. doi:10.1016/j.dam.2014.04.012[WoS][Crossref] Zbl1298.05127
- [17] I. Schiermeyer, Rainbow connection in graphs with minimum degree three, IWOCA 2009, Lecture Notes in Comput. Sci. 5874 (2009) 432-437. Zbl1267.05125
- [18] K. Uchizawa, T. Aoki, T. Ito, A. Suzuki and X. Zhou, On the rainbow connectivity of graphs: Complexity and FPT algorithms, Algorithmica 67 (2013) 161-179. doi:10.1007/s00453-012-9689-4[Crossref] Zbl1290.68060

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.