On the complexity of vertex-coloring edge-weightings

Andrzej Dudek ; David Wajc - On the complexity of vertex-coloring edge-weightingsdmtcs: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-weightingsArticle

Authors: Andrzej Dudek ¹; David Wajc ²

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]

Bibliographic References

12 Documents citing this article

Jakub Przybyło;Fan Wei, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, On asymptotic confirmation of the Faudree-Lehel Conjecture on the irregularity strength of graphs, 114, pp. 766-773, 2023, Prague, Czech Republic, 10.5817/cz.muni.eurocomb23-106.

Julien Bensmail;Foivos Fioravantes;Nicolas Nisse, 2022, On Proper Labellings of Graphs with Minimum Label Sum, 84, 4, pp. 1030-1063, 10.1007/s00453-021-00903-x, https://hal.archives-ouvertes.fr/hal-02510044.

Mingyue Xiao;Jihui Wang, 2022 International Symposium on Intelligent Robotics and Systems (ISoIRS), The Adjacent Vertex Sum Distinguishing Coloring of the Join and Cartesian Product of Some Digraphs, pp. 143-147, 2022, Chengdu, China, 10.1109/isoirs57349.2022.00036.

Antoine Dailly;Éric Duchêne;Aline Parreau;Elżbieta Sidorowicz, 2021, The neighbour sum distinguishing relaxed edge colouring, 419, pp. 126864, 10.1016/j.amc.2021.126864, https://hal.archives-ouvertes.fr/hal-03064954.

Julien Bensmail;Foivos Fioravantes;Fionn Mc Inerney, 2021, On the role of 3s for the 1-2-3 Conjecture, Theoretical Computer Science, 892, pp. 238-257, 10.1016/j.tcs.2021.09.023, https://doi.org/10.1016/j.tcs.2021.09.023.

Julien Bensmail;Foivos Fioravantes;Fionn Mc Inerney;Nicolas Nisse, 2021, Further results on an equitable 1-2-3 Conjecture, 297, pp. 1-20, 10.1016/j.dam.2021.02.037, https://hal.science/hal-02533537.

Jarosław Grytczuk, 2020, From the 1-2-3 conjecture to the Riemann hypothesis, arXiv (Cornell University), 91, pp. 103213, 10.1016/j.ejc.2020.103213, https://arxiv.org/abs/2003.02887.

Julien Bensmail;Bi Li;Binlong Li, 2020, An Injective Version of the 1-2-3 Conjecture, 37, 1, pp. 281-311, 10.1007/s00373-020-02252-y, https://hal.science/hal-02459377.

Julien Bensmail;Fionn Mc Inerney;Kasper Szabo Lyngsie, 2019, On {a,b}-edge-weightings of bipartite graphs with odd a,b, Discussiones Mathematicae Graph Theory, 42, 1, pp. 159, 10.7151/dmgt.2250, https://doi.org/10.7151/dmgt.2250.

Olivier Baudon;Julien Bensmail;Tom Davot;Hervé Hocquard;Jakub Przybyło;et al., 2019, A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions, 10.23638/dmtcs-21-1-2, https://hal.archives-ouvertes.fr/hal-01690222.

Julien Bensmail, 2018, A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graphs, Discrete Applied Mathematics, 257, pp. 31-39, 10.1016/j.dam.2018.10.008, https://doi.org/10.1016/j.dam.2018.10.008.

Hongliang Lu, 2016, Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights, Discrete Mathematics & Theoretical Computer Science, Vol. 17 no. 3, Graph Theory, 10.46298/dmtcs.2162, https://doi.org/10.46298/dmtcs.2162.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 556 times.

This article's PDF has been downloaded 560 times.