vignette|Étiquetage gracieux. Les sommets sont étiquetés en noir, les arêtes en rouge. vignette|Étiquetage gracieux d'une chaîne de 5 sommets.
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 gracieuxVirginia Vassilevska, « Coding and Graceful Labeling of trees », SURF 2001 PostScript.
Le terme « étiquetage gracieux » (en anglais ) apparaît dans un article de Solomon W. Golomb.. Le concept figure, sous le nom de « β-labeling » dans un article d'Alexander Rosa sur l’étiquetage de graphes..
Conjecture des arbres gracieux 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 :
La conjecture de Ringel-Kotzig est aussi connue sous le terme de « conjecture de l’étiquetage gracieux ».. Une version plus faible est la
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.. Le résultat a fait l'objet d'un article dans Quanta Magazine. et dans Pour la Science.
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 : Un graphe eulérien avec m arêtes n'est pas gracieux si m ≡ 1 (mod 4) ou m ≡ 2 (mod 4). Un cycle Cn à n sommets est gracieux si et seulement si n ≡ 0 (mod 4) ou n ≡ 3 (mod 4). Toutes les chaînes et tous les graphes chenilles sont gracieux. Tout graphe biparti complet est gracieux. Les arbres à au plus 27 sommets sont gracieux... Ce résultat est étendu en 2003 aux arbres à 29 sommets par Michael Horton dans sa thèse de bachelor.. Une autre extension, à 35 sommets, est annoncée en 2010 par Wenjie Fang.. Tout graphe roue, tout graphe grille est gracieux. Tout hypercube est gracieux.. 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.
Notes et références
Bibliographie . . . .
Articles liés
Liste de conjectures mathématiques
Catégorie:Théorie des graphes Catégorie:Combinatoire Catégorie:Conjecture non résolue