Skip to Main content Skip to Navigation
Journal articles

On the complexity of vertex-coloring edge-weightings

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990502
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:39:39 PM
Last modification on : Wednesday, August 7, 2019 - 2:08:08 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:17:15 PM

File

1508-6558-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990502, version 1

Collections

Citation

Andrzej Dudek, David Wajc. On the complexity of vertex-coloring edge-weightings. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.45--50. ⟨hal-00990502⟩

Share

Metrics

Record views

158

Files downloads

1036