DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

J. Bensmail

Julien Bensmail

Université Côte d'Azur

email: julien.bensmail.phd@gmail.com

0000-0002-9292-394X

Title:

On a graph labelling conjecture involving coloured labels

PDF

Source:

Discussiones Mathematicae Graph Theory 44(1) (2024) 231-244

Received: 2021-07-23 , Revised: 2021-11-15 , Accepted: 2021-11-15 , Available online: 2021-12-02 , https://doi.org/10.7151/dmgt.2441

Abstract:

In this work, we investigate a recent conjecture by Baudon, Bensmail, Davot, Hocquard, Przybyło, Senhaji, Sopena and Woźniak, which states that graphs, in general, can be edge-labelled with red labels $1,2$ and blue labels $1,2$ so that every two adjacent vertices are distinguished accordingly to either the sums of their incident red labels or the sums of their incident blue labels. To date, this was verified for several classes of graphs. Also, it is known how to design several labelling schemes that are very close to what is desired. In this work, we adapt two important proofs of the field, leading to some progress towards that conjecture. We first prove that graphs can be labelled with red labels $1,2,3$ and blue labels $1,2$ so that every two adjacent vertices are distinguished as required. We then verify the conjecture for graphs with chromatic number at most $4$.

Keywords:

proper labelling, coloured label, Weak $(2,2)$-Conjecture, 1-2-3 Conjecture

References:

  1. L. Addario-Berry, R.E.L. Aldred, K. Dalal and B.A. Reed, Vertex colouring edge partitions, J. Combin. Theory Ser. B 94 (2005) 237–244.
    https://doi.org/10.1016/j.jctb.2005.01.001
  2. O. Baudon, J. Bensmail, T. Davot, H. Hocquard, J. Przybyło, M. Senhaji, É. Sopena and 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
  3. O. Baudon, J. Bensmail, H. Hocquard, M. Senhaji and É. 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
  4. O. Baudon, J. Bensmail, J. Przybyło and M. Woźniak, On decomposing regular graphs into locally irregular subgraphs, European J. Combin. 49 (2015) 90–104.
    https://doi.org/10.1016/j.ejc.2015.02.031
  5. J. Bensmail, A $1$-$2$-$3$-$4$ result for the $1$-$2$-$3$ Conjecture in $5$-regular graphs, Discrete Appl. Math. 257 (2019) 31–39.
    https://doi.org/10.1016/j.dam.2018.10.008
  6. J. Bensmail, H. Hocquard, D. Lajou and É. Sopena, Further evidence towards the multiplicative $1$-$2$-$3$ Conjecture, Discrete Appl. Math. 307 (2022) 135–144.
    https://doi.org/https://dx.doi.org/10.1016/j.dam.2021.10.014
  7. J. Bensmail and J. Przybyło, Decomposability of graphs into subgraphs fulfilling the $1$-$2$-$3$ Conjecture, Discrete Appl. Math. 268 (2019) 1–9.
    https://doi.org/10.1016/j.dam.2019.04.011
  8. G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197–210.
  9. J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2017) #DS6, http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6/versions.
  10. Y. Gao, G. Wang and 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
  11. M. Kalkowski, A note on the $1,2$-Conjecture, Electron. J. Combin., in press.
  12. M. Kalkowski, M. Karoński and F. Pfender, Vertex-coloring edge-weightings: Towards the $1$-$2$-$3$ Conjecture, J. Combin. Theory Ser. B 100 (2010) 347–349.
    https://doi.org/10.1016/j.jctb.2009.06.002
  13. M. Kalkowski, M. Karoński and F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math. 25 (2011) 1319–1321.
    https://doi.org/10.1137/090774112
  14. M. Karoński, T. Łuczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004) 151–157.
    https://doi.org/10.1016/j.jctb.2003.12.001
  15. J. Przybyło, A note on the weak $(2,2)$-Conjecture, Discrete Math. 342 (2019) 498–504.
    https://doi.org/10.1016/j.disc.2018.10.033
  16. J. Przybyło, The $1$-$2$-$3$ Conjecture almost holds for regular graphs, J. Combin. Theory Ser. B 147 (2021) 183–200.
    https://doi.org/10.1016/j.jctb.2020.03.005
  17. B. Seamone, The $1$-$2$-$3$ Conjecture and related problems: a survey (2012).
    http://arxiv.org/abs/1211.5122
  18. B. Vučković, Multi-set neighbor distinguishing $3$-edge coloring, Discrete Math. 341 (2018) 820–824.
    https://doi.org/10.1016/j.disc.2017.12.001
Close