Accéder directement au contenu Accéder directement à la navigation
Rapport

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

Julien Bensmail 1 Foivos Fioravantes 1 Fionn Mc Inerney 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ACRO - Algorithmique, Combinatoire et Recherche Opérationnelle
LIS - Laboratoire d'Informatique et Systèmes
Abstract : The 1-2-3 Conjecture states that every connected graph different from K2 admits a proper 3-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 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 3's in their proper 3-labellings. Actually, deciding whether a given graph can be properly 3-labelled with p 3's 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 they all 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 needed 3's.
Type de document :
Rapport
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-02975031
Contributeur : Julien Bensmail <>
Soumis le : jeudi 22 octobre 2020 - 12:19:49
Dernière modification le : jeudi 29 octobre 2020 - 03:31:40

Fichier

role3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02975031, version 1

Citation

Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney. On the Role of 3's for the 1-2-3 Conjecture. [Research Report] Université côte d'azur; Aix-Marseille Université. 2020. ⟨hal-02975031v1⟩

Partager

Métriques

Consultations de la notice

44

Téléchargements de fichiers

20