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