Andrzej Dudek ; David Wajc - On the complexity of vertex-coloring edge-weightings

dmtcs:548 - Discrete Mathematics & Theoretical Computer Science, November 6, 2011, Vol. 13 no. 3 - https://doi.org/10.46298/dmtcs.548
On the complexity of vertex-coloring edge-weightings

Authors: Andrzej Dudek 1; David Wajc 2

  • 1 Department of Mathematics [Kalamazoo]
  • 2 Department of Computer Science [Haifa]

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.

https://doi.org/10.46298/dmtcs.548
Source: HAL:hal-00990502v1
Volume: Vol. 13 no. 3
Section: Graph and Algorithms
Published on: November 6, 2011
Accepted on: June 9, 2015
Submitted on: March 18, 2010
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

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
  • 10.48550/arxiv.1701.00927
  • 1701.00927
  • 10.23638/dmtcs-20-1-21
On neighbour sum-distinguishing {0,1}-weightings of bipartite graphs

Share and export

Consultation statistics

This page has been seen 337 times.
This article's PDF has been downloaded 393 times.