Hardness Results for Total Rainbow Connection of Graphs

Lily 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 -