Given a graph G = (V; E) and a weight function omega : E -\textgreater R, a coloring of vertices of G, induced by omega, is defined by chi(omega) (nu) = Sigma(e(sic)nu) omega (e) for all nu is an element of 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.

Source : oai:HAL:hal-00990502v1

Volume: Vol. 13 no. 3

Section: Graph and Algorithms

Published on: November 6, 2011

Submitted on: March 18, 2010

Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 83 times.

This article's PDF has been downloaded 168 times.