Geodesic
On a graph labelling conjecture involving coloured labels
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 231-244

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2024_44_1_a10,
     author = {Bensmail, Julien},
     title = {On a graph labelling conjecture involving coloured labels},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {231--244},
     publisher = {mathdoc},
     volume = {44},
     number = {1},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a10/}
}
TY  - JOUR
AU  - Bensmail, Julien
TI  - On a graph labelling conjecture involving coloured labels
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 231
EP  - 244
VL  - 44
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a10/
LA  - en
ID  - DMGT_2024_44_1_a10
ER  - 
%0 Journal Article
%A Bensmail, Julien
%T On a graph labelling conjecture involving coloured labels
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 231-244
%V 44
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a10/
%G en
%F DMGT_2024_44_1_a10
Bensmail, Julien. On a graph labelling conjecture involving coloured labels. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 231-244. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a10/