96-05
On the Complexity of Line-Distinguishing-Coloring of Simple Graphs
Preprint series: 96-05, Preprints
Abstract: In this paper we consider the line\xaddistinguishing coloring of sim\xadple graphs. The line-distinguishing chromatic number is the smallestnumber of colors which is necessary to color the vertices of a simplegraph where each pair of colors appears together on an edge at mostonce. The complexity status of this problem was still open. We showthe NP\xadhardness of this problem by reduction from the harmoniouscoloring of a simple graph.
Keywords: Line\xaddistinguishing Coloring, Complexity, NP\xadhard