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/