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