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

## NotesEmbed ?

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