Discrete Mathematics & Theoretical Computer Science, Vol 13, No 3 (2011)

Font Size:  Small  Medium  Large

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