Nombre de Thue
# Nombre de Thue

Dans le domaine mathématique de la théorie des graphes, le nombre de Thue d'un graphe est une variante de l'indice chromatique, définie par Alon et ses coauteurs en 2002, et appelée du nom du mathématicien Axel Thue, qui a étudié les mots sans carrés utilisés pour définir ce nombre.

## Définition

Une coloration non répétitive d'un graphe est une affectation de couleurs aux arêtes du graphe telle qu'il n'existe pas de chaîne longueur paire dans laquelle les couleurs des arêtes dans la première moitié de la chaîne forment la même suite que les couleurs des arêtes de la seconde moitié de la chaîne. Le nombre de Thue d'un graphe est le nombre minimum de couleurs nécessaires dans une coloration non répétitive.

Au lieu de la coloration des arêtes, on peut considérer la coloration des sommets d'un graphe, par des couleurs ou des listes de couleurs. On appelle nombre chromatique non répétitif le plus petit nombre de couleurs nécessaires pour colorer les sommets d'un graphe de sorte que les couleurs des sommets de toute chaîne sont sans facteur carré. Fiorenzi, Ochem et al. étudient des listes de couleurs pour les arbres.

Des variations de ces notions ont été étudiées dans plusieurs articles, notamment de Barát et Varjú (2008), Barát et Wood (2005), Brešar et Klavžar (2004), et Kündgen et Pelsmajer (2008). Un article de synthèse des premiers résultats a été publié par Jaroslaw Grytczuk en 2007. Une autre bibliographie détaillée est donnée par Dujmović, Esperet et al..

## Exemple

Un pentagone est un cycle de cinq sommets noté C $_5.$ Si on colorie ses arêtes avec deux couleurs, il y a deux arêtes adjacentes avec la même couleur x ; le chemin formé par ces deux arêtes est la suite de couleurs répétitive xx. Si on utilise trois couleurs, l'une des trois couleurs n'est utilisée qu'une seule fois ; le chemin de quatre arêtes formé par les arêtes des deux autres couleurs a soit deux arêtes consécutives de même couleur, soit donne la séquence de couleurs répétées xyxy. Cependant, avec quatre couleurs, il n'est pas difficile d'éviter toute répétition. Par conséquent le nombre de Thue de C $_5$ est quatre.

## Résultats

Alon et al. utilisent le lemme local de Lovász pour prouver que le nombre de Thue de tout graphe est majoré par le carré de son degré maximum ; ils fournissent un exemple montrant que pour certains graphes, cette majoration quadratique est atteinte. De plus, ils montrent que le nombre de Thue de toute chaîne de longueur au moins quatre est exactement trois, que le nombre de Thue de tout cycle est au plus quatre, et que le nombre de Thue du graphe de Petersen est exactement cinq.

### Cycles

Les cycles dont on sait que le nombre de Thue est quatre sont C $_5,$ C $_7,$ C $_9,$ C $_{10},$ C $_{14}$ et C $_{17}$ . Alon et al. ont conjecturé que le nombre de Thue de tout cycle plus long est trois. Currie a résolu cette conjecture en 2002 en montrant que tous les cycles avec 18 sommets ou plus ont le nombre de Thue 3.

### Graphes planaires

La recherche d'une majoration du nombre de Thue des graphes planaires a abouti en 2020 à un article de Dujmović, Esperet et al. ; ils résolvent une conjecture déjà formulée par Grytczuk et montrent que le nombre de Thue des graphes planaires est borné ; plus précisément, ils montrent que le nombre de Thue de tout graphe planaire est au plus 768. Ils donnent aussi des majorations pour d'autres classes plus générales, les graphes de genre borné, les graphes excluant un mineur excluant un mineur fixe, et les graphes excluant un mineur topologique fixe. Ainso, ils montrent que tout graphe de genre g a un nombre de Thue majoré par 256 max(2g,3), et que pour tout graphe X, il existe un entier k tel que tout graphe à mineur X exclua un nombre de Thue majoré par k.

### Coloration des sommets

Plusieurs classes de graphes ont un nombre chromatique non répétitif bornés. En particulier, les cycles sont non répétitivement 3-colorables (sauf pour un nombre fini d'exceptions) , les arbres sont non répétitivement $4-colorables^,,$ les graphes planaires extérieurs sont non répétitivement $12-colorables^,,$ et plus généralement, tout graphe de largeur arborescente $k$ est non répétitivement $4^{k}$-colorable. Les graphes de degré maximal ∆ sont non répétitivement $O(\Delta ^{2})$$-colorables^,^,^,^,$ ; les graphes qui excluent une immersion fixe ont un nombre chromatique non répétitif borné.

## Complexité de calcul

Tester si une coloration possède un chemin répétitif est dans la classe NP, donc tester si une coloration est non répétitive est en co-NP, et Fedor Manin a montré que le problème est co-NP-complet. Le problème de trouver une telle coloration appartient à $\Sigma _{2}^{P}$ dans la hiérarchie polynomiale, et à nouveau Manin a montré qu'il est complet pour ce niveau.

