Étiquetage gracieux
# É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 :

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 ». Une version plus faible est la

Conjecture de Ringel — Le graphe complet $K_{2n+1}$ peut être décomposé en copies de tout arbre à $n$ arêtes.

Cette conjecture de Ringel a été démontrée pour des grandes valeurs de $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_5;$ et le graphe graphe papillon.
