concept De Wikipédia, l'encyclopédie libre
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]
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] :
Seamless Wikipedia browsing. On steroids.
