Geodesic
Hardness Results for Total Rainbow Connection of Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 355-362.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: total rainbow connection, computational complexity 
@article{DMGT_2016_36_2_a7,
     author = {Chen, Lily and Huo, Bofeng and Ma, Yingbin},
     title = {Hardness {Results} for {Total} {Rainbow} {Connection} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {355--362},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a7/}
}
TY  - JOUR
AU  - Chen, Lily
AU  - Huo, Bofeng
AU  - Ma, Yingbin
TI  - Hardness Results for Total Rainbow Connection of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 355
EP  - 362
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a7/
LA  - en
ID  - DMGT_2016_36_2_a7
ER  - 
%0 Journal Article
%A Chen, Lily
%A Huo, Bofeng
%A Ma, Yingbin
%T Hardness Results for Total Rainbow Connection of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 355-362
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a7/
%G en
%F DMGT_2016_36_2_a7
Chen, Lily; Huo, Bofeng; Ma, Yingbin. Hardness Results for Total Rainbow Connection of Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 355-362. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a7/

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

[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

[4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98.

[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

[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

[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

[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

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

[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

[11] X. Li, Y. Mao and Y. Shi, The strong rainbow vertex-connection of graphs, Util. Math. 93 (2014) 213-223.

[12] X. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory 33 (2013) 307-313. doi:10.7151/dmgt.1664

[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

[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

[15] X. Li and Y. Sun, Rainbow Connections of Graphs (New York, Springer Briefs in Math., Springer, 2012).

[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

[17] I. Schiermeyer, Rainbow connection in graphs with minimum degree three, IWOCA 2009, Lecture Notes in Comput. Sci. 5874 (2009) 432-437.

[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