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.
@article{bwmeta1.element.doi-10_7151_dmgt_1856,
author = {Lily Chen and Bofeng Huo and Yingbin Ma},
title = {Hardness Results for Total Rainbow Connection of Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {355-362},
zbl = {1338.05077},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1856}
}
Lily Chen; Bofeng Huo; Yingbin Ma. Hardness Results for Total Rainbow Connection of Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 355-362. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1856/