![]() |
Discrete Mathematics & Theoretical Computer Science |
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 : ScholeXplorer
IsRelatedTo ARXIV 1701.00927 Source : ScholeXplorer IsRelatedTo DOI 10.23638/dmtcs-20-1-21 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1701.00927
|