On the Role of 3s for the 1-2-3 Conjecture - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2021

On the Role of 3s for the 1-2-3 Conjecture

Résumé

The 1-2-3 Conjecture states that every connected graph different from K2 admits a proper 3-(edge-)labelling, i.e., can have its edges labelled with 1,2,3 so that no two adjacent vertices are incident to the same sum of labels. In connection with some recent optimisation variants of this conjecture, in this paper we investigate the role of the label 3 in proper 3-labellings of graphs. An intuition from previous investigations is that, in general, it should always be possible to produce proper 3-labellings assigning label 3 to a only few edges. We prove that, for every p≥0, there are various graphs needing at least p 3s in their proper 3-labellings. Actually, deciding whether a given graph can be properly 3-labelled with p 3s is NP--complete for every p≥0. We also focus on classes of 3-chromatic graphs. For various classes of such graphs (cacti, cubic graphs, triangle-free planar graphs, etc.), we prove that there is no p≥1 such that all their graphs admit proper 3-labellings assigning label 3 to at most p edges. In such cases, we provide lower and upper bounds on the number of 3s needed.
Fichier principal
Vignette du fichier
main.pdf (655.19 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02975031 , version 1 (22-10-2020)
hal-02975031 , version 2 (23-10-2020)
hal-02975031 , version 3 (02-08-2021)

Identifiants

Citer

Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney. On the Role of 3s for the 1-2-3 Conjecture. Theoretical Computer Science, 2021, 892, pp.238-257. ⟨10.1016/j.tcs.2021.09.023⟩. ⟨hal-02975031v3⟩
266 Consultations
180 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More