Opuscula Math. 46, no. 2 (2026), 127-137
https://doi.org/10.7494/OpMath.202602101

 
Opuscula Mathematica

Some remarks and results on the Standard (2,2)-Conjecture

Olivier Baudon
Julien Bensmail
Lyn Vayssieres

Abstract. In this note, we prove that every graph can be edge-labelled with red labels \(1,2\) and blue labels \(1,2\) so that vertices with any sum of incident red labels induce a \(1\)-degenerate graph, while vertices with any sum of incident blue labels induce a \(0\)-degenerate graph. This result stands as a closer step towards the so-called Standard \((2,2)\)-Conjecture (stating that \(0\)-degeneracy can be achieved in both colours), and provides some insight on the surrounding field, which covers the 1-2-3 Conjecture, the 1-2 Conjecture, and other close problems. Along the way, we also describe how many related problems are interconnected, and raise new problems and questions for further work on the topic.

Keywords: 1-2-3 Conjecture, 1-2 Conjecture, proper labelling, labelling.

Mathematics Subject Classification: 05C78, 05C15, 68R10.

Full text (pdf)

  1. O. Baudon, J. Bensmail, T. Davot, H. Hocquard, J. Przybyło, M. Senhaji, É. Sopena, M. Woźniak, A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions, Discrete Math. Theor. Comput. Sci. 21 (2019), #2. https://doi.org/10.23638/dmtcs-21-1-2
  2. O. Baudon, J. Bensmail, H. Hocquard, M. Senhaji, É. Sopena, Edge weights and vertex colours: Minimizing sum count, Discrete Appl. Math. 270 (2019), 13-24. https://doi.org/10.1016/j.dam.2019.07.019
  3. J. Bensmail, On a graph labelling conjecture involving coloured labels, Discuss. Math. Graph Theory 44 (2024), 231-244. https://doi.org/10.7151/dmgt.2441
  4. J. Bensmail, M. Boivin, I. Grzelec, C. Marcille, The Strong \((2,2)\)-Conjecture for more classes of graphs, Discrete Appl. Math. 382 (2026), 337-354. https://doi.org/10.1016/j.dam.2025.12.011
  5. J. Bensmail, R. Bourneuf, P. Colinot, S. Humeau, T. Martinod, Making graphs irregular through irregularising walks, Theor. Comput. Sci. (2026), in press. https://doi.org/10.1016/j.tcs.2026.115773
  6. J. Bensmail, F. Fioravantes, F. Mc Inerney, On the role of 3s for the 1-2-3 Conjecture, Theor. Comput. Sci. 892 (2021), 238-257. https://doi.org/10.1016/j.tcs.2021.09.023
  7. J. Bensmail, H. Hocquard, D. Lajou, É. Sopena, A proof of the Multiplicative 1-2-3 Conjecture, Combinatorica 43 (2023), 37-55. https://doi.org/10.1007/s00493-023-00003-0
  8. J. Bensmail, H. Hocquard, P.-M. Marcille, On inducing degenerate sums through 2-labellings, Graphs Combin. 40 (2024), Article no. 23. https://doi.org/10.1007/s00373-024-02758-9
  9. J. Bensmail, B. Li, B. Li, An injective version of the 1-2-3 Conjecture, Graphs Combin. 37 (2021), 281-311. https://doi.org/10.1007/s00373-020-02252-y
  10. J. Bensmail, B. Li, B. Li, N. Nisse, On minimizing the maximum color for the 1-2-3 Conjecture, Discrete Appl. Math. 289 (2021), 32-51. https://doi.org/10.1016/j.dam.2020.09.020
  11. J. Bensmail, F. Mc Inerney, K. Szabo Lyngsie, On \(\{a,b\}\)-edge-weightings of bipartite graphs with odd \(a,b\), Discuss. Math. Graph Theory 42 (2022), 159-185. https://doi.org/10.7151/dmgt.2250
  12. K. Deng, H. Qiu, The 1-2 conjecture holds for regular graphs, J. Comb. Theory B 174 (2025), 207-213. https://doi.org/10.1016/j.jctb.2025.05.002
  13. K. Deng, H. Qiu, Every graph is uniform-span \((2,2)\)-choosable: Beyond the 1-2 conjecture, arXiv:2506.14253 [math.CO].
  14. A. Dudek, D. Wajc, On the complexity of vertex-coloring edge-weightings, Discrete Math. Theor. Comput. Sci. 13 (2011), 45-50. https://doi.org/10.46298/dmtcs.548
  15. Y. Gao, G. Wang, J. Wu, A relaxed case on 1-2-3 Conjecture, Graphs Combin. 32 (2016), 1415-1421. https://doi.org/10.1007/s00373-015-1656-9
  16. M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours, J. Comb. Theory B 91 (2004), 151-157. https://doi.org/10.1016/j.jctb.2003.12.001
  17. R. Keusch, A solution to the 1-2-3 Conjecture, J. Comb. Theory B 166 (2024), 183-202. https://doi.org/10.1016/j.jctb.2024.01.002
  18. K.S. Lyngsie, On neighbour sum-distinguishing \(\{0,1\}\)-weightings of bipartite graphs, Discrete Math. Theor. Comput. Sci. 20 (2018), #21. https://doi.org/10.23638/dmtcs-20-1-21
  19. J. Przybyło, On the standard \((2,2)\)-conjecture, Eur. J. Comb. 94 (2021), 103305. https://doi.org/10.1016/j.ejc.2020.103305
  20. J. Przybyło, M. Woźniak, On a \(1,2\) Conjecture, Discrete Math. Theor. Comput. Sci. 12 (2010), 101-108. https://doi.org/10.46298/dmtcs.491
  21. B. Seamone, The 1-2-3 Conjecture and related problems: a survey, arXiv:1211.5122 [math.CO].
  22. C. Thomassen, Y. Wu, C.-Q. Zhang, The \(3\)-flow conjecture, factors modulo \(k\), and the 1-2-3-conjecture, J. Comb. Theory B 121 (2016), 308-325. https://doi.org/10.1016/j.jctb.2016.06.010
  • Lyn Vayssieres
  • Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France
  • Communicated by Andrzej Żak.
  • Received: 2025-08-27.
  • Revised: 2026-01-22.
  • Accepted: 2026-02-10.
  • Published online: 2026-04-10.
Opuscula Mathematica - cover

Cite this article as:
Olivier Baudon, Julien Bensmail, Lyn Vayssieres, Some remarks and results on the Standard (2,2)-Conjecture, Opuscula Math. 46, no. 2 (2026), 127-137, https://doi.org/10.7494/OpMath.202602101

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise that this website uses cookies to help us understand how the site is used. All data is anonymized. Recent versions of popular browsers provide users with control over cookies, allowing them to set their preferences to accept or reject all cookies or specific ones.