Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the complexity of ...
Article

On the complexity of vertex-coloring edge-weightings

Andrzej Dudek (1), David Wajc (2)
(1) Department of Mathematics [Kalamazoo]
(2) Department of Computer Science [Haifa]
Download article
Open on HAL
Imported on
March 17, 2010
Published on
November 5, 2011
Last modified on
March 31, 2025
Volume 13
vol. 13:3
Graph and Algorithms
DOI
10.46298/dmtcs.548
License
https://about.hal.science/hal-authorisation-v1
Indicators
1105
Views
1060
Downloads

On the complexity of vertex-coloring edge-weightings

Andrzej Dudek (1), David Wajc (2)
(1) Department of Mathematics [Kalamazoo]
(2) Department of Computer Science [Haifa]
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graphs

    Authors : Julien Bensmail ORCID

    Journal reference : Volume 257, 2018, pp. 31-39

    DOI : 10.1016/j.dam.2018.10.008
  • The neighbour sum distinguishing relaxed edge colouring

    Authors : Antoine Dailly, Éric Duchêne ORCID, Aline Parreau ORCID, Elżbieta Sidorowicz ORCID

    Journal reference : Volume 419, 2021, pp. 126864

    DOI : 10.1016/j.amc.2021.126864
  • On asymptotic confirmation of the Faudree-Lehel Conjecture on the irregularity strength of graphs

    Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications

    Authors : Jakub Przybyło ORCID, Fan Wei

    Journal reference : Volume , 2023, pp. 766-773

    DOI : 10.5817/cz.muni.eurocomb23-106
  • From the 1-2-3 conjecture to the Riemann hypothesis

    arXiv (Cornell University)

    Authors : Jarosław Grytczuk ORCID

    Journal reference : Volume 91, 2020, pp. 103213

    DOI : 10.1016/j.ejc.2020.103213
  • An Injective Version of the 1-2-3 Conjecture

    Graphs and Combinatorics

    Authors : Julien Bensmail ORCID, Bi Li ORCID, Binlong Li ORCID

    Journal reference : Volume 37, 2020, pp. 281-311

    DOI : 10.1007/s00373-020-02252-y
  • On Proper Labellings of Graphs with Minimum Label Sum

    Authors : Julien Bensmail ORCID, Foivos Fioravantes ORCID, Nicolas Nisse ORCID

    Journal reference : Volume 84, 2022, pp. 1030-1063

    DOI : 10.1007/s00453-021-00903-x
  • Further results on an equitable 1-2-3 Conjecture

    INRIA a CCSD electronic archive server

    Authors : Julien Bensmail ORCID, Foivos Fioravantes ORCID, Fionn Mc Inerney ORCID, Nicolas Nisse ORCID

    Journal reference : Volume 297, 2021, pp. 1-20

    DOI : 10.1016/j.dam.2021.02.037
  • The Adjacent Vertex Sum Distinguishing Coloring of the Join and Cartesian Product of Some Digraphs

    2022 International Symposium on Intelligent Robotics and Systems (ISoIRS)

    Authors : Mingyue Xiao ORCID, Jihui Wang ORCID

    Journal reference : Volume , 2022, pp. 143-147

    DOI : 10.1109/isoirs57349.2022.00036
  • The 1,2,3-Conjecture for powers of paths and powers of cycles

    Anais do II Encontro de Teoria da Computação (ETC 2017)

    Authors : Atílio G. Luiz ORCID, C. N. Campos ORCID

    Journal reference : Volume , 2017, pp. 41-44

    DOI : 10.5753/etc.2017.3187
  • A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions

    Discrete Mathematics & Theoretical Computer Science

    Authors : Olivier Baudon ORCID, Julien Bensmail ORCID, Tom Davot ORCID, Hervé Hocquard ORCID, Jakub Przybyło ORCID, Mohammed Senhaji ORCID, Eric Sopena ORCID, Mariusz Woźniak ORCID

    Journal reference : Volume vol. 21 no. 1, ICGT 2018, 2019, pp.

    DOI : 10.23638/dmtcs-21-1-2
  • On {a,b}-edge-weightings of bipartite graphs with odd a,b

    Discussiones Mathematicae Graph Theory

    Authors : Julien Bensmail ORCID, Fionn Mc Inerney ORCID, Kasper Szabo Lyngsie ORCID

    Journal reference : Volume 42, 2019, pp. 159

    DOI : 10.7151/dmgt.2250
  • Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights

    Discrete Mathematics & Theoretical Computer Science

    Authors : Hongliang Lu ORCID

    Journal reference : Volume Vol. 17 no. 3, 2016, pp.

    DOI : 10.46298/dmtcs.2162
  • On the role of 3s for the 1-2-3 Conjecture

    Theoretical Computer Science

    Authors : Julien Bensmail ORCID, Foivos Fioravantes ORCID, Fionn Mc Inerney ORCID

    Journal reference : Volume 892, 2021, pp. 238-257

    DOI : 10.1016/j.tcs.2021.09.023
Preview
Loading PDF preview...