On the complexity of vertex-coloring edge-weightings

Andrzej Dudek; David Wajc

doi:10.46298/dmtcs.548

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-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

13 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, 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, Lecture notes in computer science, 84, 4, pp. 1030-1063, 10.1007/s00453-021-00903-x, https://doi.org/10.1007/978-3-030-48966-3_5.

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, European Journal of Combinatorics, 91, pp. 103213, 10.1016/j.ejc.2020.103213, https://doi.org/10.1016/j.ejc.2020.103213.

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, Discrete Mathematics & Theoretical Computer Science, vol. 21 no. 1, ICGT 2018, 10.23638/dmtcs-21-1-2, https://doi.org/10.23638/dmtcs-21-1-2.

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.

Atílio G. Luiz;C. N. Campos, Anais do II Encontro de Teoria da Computação (ETC 2017), The 1,2,3-Conjecture for powers of paths and powers of cycles, pp. 41-44, 2017, Brasil, 10.5753/etc.2017.3187.

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 618 times.

This article's PDF has been downloaded 601 times.