Étiquetage gracieux

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^,.

Le terme « étiquetage gracieux » (en anglais « graceful labeling ») 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 ${\displaystyle n}$ dans un article posté le 8 janvier 2020 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 C_n à 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 K₅; et le graphe graphe papillon.

Notes et références

• (de)/(en) Cet article est partiellement ou en totalité issu des articles intitulés en allemand « Graziöse Beschriftung » (voir la liste des auteurs) et en anglais « Graceful labeling » (voir la liste des auteurs).

Bibliographie

• Shalom Eliahou, « Le sudoku arboricole », Images des mathématiques : La recherche mathématique en mots et en images, CNRS, 21 décembre 2013 (consulté le 5 décembre 2017).
• « Tous les arbres sont-ils gracieux ? », k a f e m a t h 2016-2017, 29 septembre 2016 (consulté le 5 décembre 2017).
• Vasanti N. Bhat-Nayak et Ujwala N. Deshmukh, « Gracefulness of ${\displaystyle C_{4t}\cup K_{1,4t-1}}$ and ${\displaystyle C_{4t 3}\cup K_{1,4t 2}}$ », J. Ramanujan Math. Soc., vol. 11, n^o 2,‎ 1996, p. 187-190 (zbMATH 0867.05057).
• Vasanti N. Bhat-Nayak et A. Selvam, « Gracefulness of ${\displaystyle n}$-cone ${\displaystyle C_{m}\vee K_{n}^{c}}$ », Ars Combin., vol. 66,‎ 2003, p. 283–298 (MR 1961491).
• (en) Eric W. Weisstein, « Graceful graph », sur MathWorld
• Ping Zhang, A Kaleidoscopic view of graph colorings, Springer, coll. « SpringerBriefs in Mathematics », 2016, 157 p. (ISBN 978-3-319-30518-9, lire en ligne)

Articles liés

• Edge-graceful labeling (en)
• Liste de conjectures mathématiques

• Portail des mathématiques
• Portail de l'informatique théorique