Series: 1996-05, Preprints
Abstract:
this paper we consider the linedistinguishing 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 NPhardness of this problem by reduction from the harmonious
coloring of a simple graph.
Keywords:
Linedistinguishing Coloring, Complexity, NPhard