Étiquetage gracieux
From Wikipedia, the free encyclopedia
En théorie des graphes, un étiquetage gracieux d'un graphe non orienté à m arêtes est un étiquetage de ses sommets par des entiers naturels distincts pris dans l'ensemble {0,...,m} qui a la propriété que les valeurs absolues des différences des étiquettes des extrémités des arêtes sont toutes distinctes et égales à 1,...,m ; elles identifient ainsi de manière unique les arêtes. Un graphe qui admet un étiquetage gracieux est un graphe gracieux[1],[2].
Le terme « étiquetage gracieux » (en anglais « graceful labeling ») apparaît dans un article de Solomon W. Golomb[3],[4] Le concept figure, sous le nom de « β-labeling » dans un article d'Alexander Rosa sur l’étiquetage de graphes[5].
Une des conjectures non résolues en théorie des graphes est la conjecture des arbres gracieux ou conjecture de Ringel-Kotzig, nommée ainsi d'après Gerhard Ringel and Anton Kotzig. Elle affirme :
Conjecture de Ringel-Kotzig — Tous les arbres sont gracieux.
La conjecture de Ringel-Kotzig est aussi connue sous le terme de « conjecture de l’étiquetage gracieux »[6]. Une version plus faible est la
Conjecture de Ringel — Le graphe complet peut être décomposé en copies de tout arbre à arêtes.
Cette conjecture de Ringel a été démontrée pour des grandes valeurs de dans un article posté le par Richard Montgomery, Alexey Pokrovskiy et Benny Sudakov sur Arxiv[7]. Le résultat a fait l'objet d'un article dans Quanta Magazine[8] et dans Pour la Science[9]
Résultats partiels
De nombreux résultats partiels — positifs ou négatifs — concernent des classes particulières de graphes. Un catalogue est maintenu par Joseph A. Gallian[10] :
- Un graphe eulérien avec m arêtes n'est pas gracieux si m ≡ 1 (mod 4) ou m ≡ 2 (mod 4)[5].
- Un cycle Cn à n sommets est gracieux si et seulement si n ≡ 0 (mod 4) ou n ≡ 3 (mod 4)[5].
- Toutes les chaînes et tous les graphes chenilles sont gracieux.
- Tout graphe biparti complet est gracieux[1].
- Les arbres à au plus 27 sommets sont gracieux[10],[11]. Ce résultat est étendu en 2003 aux arbres à 29 sommets par Michael Horton dans sa thèse de bachelor[12]. Une autre extension, à 35 sommets, est annoncée en 2010 par Wenjie Fang[13].
- Tout graphe roue, tout graphe grille est gracieux[10].
- Tout hypercube est gracieux[14].
- Les graphes simples avec au plus quatre sommets sont gracieux. Les seuls graphes à 5 sommets qui ne sont pas gracieux sont le 5-cycle (le pentagone); le graphe complet K5; et le graphe graphe papillon[1].
