1. bookAHEAD OF PRINT
Detalles de la revista
License
Formato
Revista
eISSN
2083-5892
Primera edición
13 Apr 2013
Calendario de la edición
4 veces al año
Idiomas
Inglés
access type Acceso abierto

On a Graph Labelling Conjecture Involving Coloured Labels

Publicado en línea: 10 Jan 2022
Volumen & Edición: AHEAD OF PRINT
Páginas: -
Recibido: 23 Jul 2021
Aceptado: 15 Nov 2021
Detalles de la revista
License
Formato
Revista
eISSN
2083-5892
Primera edición
13 Apr 2013
Calendario de la edición
4 veces al año
Idiomas
Inglés
Abstract

In this work, we investigate a recent conjecture by Baudon, Bensmail, Davot, Hocquard, Przyby lo, 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

MSC 2010

[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.00110.1016/j.jctb.2005.01.001 Search in Google Scholar

[2] O. Baudon, J. Bensmail, T. Davot, H. Hocquard, J. Przyby lo, 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 Search in Google Scholar

[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.01910.1016/j.dam.2019.07.019 Search in Google Scholar

[4] O. Baudon, J. Bensmail, J. Przyby lo 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.03110.1016/j.ejc.2015.02.031 Search in Google Scholar

[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.00810.1016/j.dam.2018.10.008 Search in Google Scholar

[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.01410.1016/j.dam.2021.10.014 Search in Google Scholar

[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.01110.1016/j.dam.2019.04.011 Search in Google Scholar

[8] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197–210. Search in Google Scholar

[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/versions10.37236/27 Search in Google Scholar

[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-910.1007/s00373-015-1656-9 Search in Google Scholar

[11] M. Kalkowski, A note on the 1, 2-Conjecture, Electron. J. Combin., in-press. Search in Google Scholar

[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.00210.1016/j.jctb.2009.06.002 Search in Google Scholar

[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/09077411210.1137/090774112 Search in Google Scholar

[14] M. Karoński, T. Luczak 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.00110.1016/j.jctb.2003.12.001 Search in Google Scholar

[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.03310.1016/j.disc.2018.10.033 Search in Google Scholar

[16] J. Przyby lo, 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.00510.1016/j.jctb.2020.03.005 Search in Google Scholar

[17] B. Seamone, The 1-2-3 Conjecture and related problems: a survey (2012). http://arxiv.org/abs/1211.5122 Search in Google Scholar

[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.00110.1016/j.disc.2017.12.001 Search in Google Scholar

Artículos recomendados de Trend MD

Planifique su conferencia remota con Sciendo