On the complexity of vertex-coloring edge-weightings
Andrzej Dudek, David Wajc
Abstract
Given a graph G=(V,E) and a weight function w:E
→R, a coloring of vertices
of G, induced by w, is defined by
χw(v) = ∑e∋v w(e) for
all v∈V. In this paper, we show that determining
whether a particular graph has a weighting of the edges from
{1,2} that induces a proper vertex coloring
is NP-complete.
Full Text: PDF PostScript