Zurück zu den Preprints des Jahres 1996


On the Complexity of Line-Distinguishing-Coloring of Simple Graphs

by Bräsel, H., Hadwich, V..

Series: 1996-05, Preprints


this paper we consider the line­distinguishing coloring of sim­
ple graphs. The line-distinguishing chromatic number is the smallest
number of colors which is necessary to color the vertices of a simple
graph where each pair of colors appears together on an edge at most
once. The complexity status of this problem was still open. We show
the NP­hardness of this problem by reduction from the harmonious
coloring of a simple graph.

Line­distinguishing Coloring, Complexity, NP­hard