Graphe roue
# Graphe roue

En théorie des graphes, le graphe roue $W_n$ est un graphe d'ordre $n\geq 4$ formé en ajoutant un sommet « centre » connecté à tous les sommets du graphe cycle $C_{n-1}.$ La notation $W_n$ provient du nom anglais wheel graph mais n'est pas universelle. Certains auteurs préfèrent $W_{n-1},$ faisant référence à la longueur du cycle.

## Propriétés

### Propriétés générales

Pour les valeurs impaires de n, le graphe $W_n$ est un graphe parfait. Quand n est pair et supérieur ou égal à 6, le graphe roue $W_n$ n'est pas parfait.

Le nombre de cycles dans le graphe roue $W_n$ est égal à $n^{2}-3n+3$ (suite A002061 de l'OEIS) : 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, 273, 307, 343, 381, 421, 463, 507 (pour n=4, 5, 6,…). De plus le graphe roue contient toujours un cycle hamiltonien. Quel que soit n, sa maille, la longueur de son plus court cycle, est 3.

Le graphe roue est planaire. Il a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête n'en croise une autre. À partir de cette représentation, il est possible de définir son graphe dual. C'est le graphe dont les sommets correspondent aux faces du graphe roue et où deux sommets sont adjacents s'ils correspondent à deux faces adjacentes. Le dual du graphe roue $W_n$ est $W_n$ lui-même, faisant du graphe roue un graphe autodual. Tout graphe planaire maximal autre que le graphe complet $K_4$ = $W_4,$ contient comme sous-graphe ou $W_5$ ou $W_6.$

$W_7$ est le seul graphe roue à être distance-unité.

Le graphe roue $W_6$ est un contre-exemple à une conjecture de Paul Erdős sur la théorie de Ramsey. Erdős avait conjecturé que le graphe complet avait le plus petit nombre de Ramsey parmi tous les graphes avec le même nombre chromatique, mais Faudree et McKay montrèrent en 1993 que $W_6$ a un nombre de Ramsey égal à 17 alors que le graphe complet avec le même nombre chromatique, $K_4,$ a un nombre de Ramsey égal à 18. En effet, pour tout graphe G d'ordre 17, G ou son complément contient un sous-graphe isomorphe à $W_6,$ alors que ni le graphe de Paley d'ordre 17 ni son complément ne contiennent un sous-graphe isomorphe à $K_4.$

### Coloration

Pour les valeurs impaires de n, le graphe $W_n$ a un nombre chromatique de 3 : les sommets du cycle $C_{n-1}$ peuvent être colorées avec deux couleurs et le centre se voit attribuer la troisième couleur. Pour n pair le graphe à un nombre chromatique égal à 4 : les sommets du cycle $C_{n-1}$ nécessitent trois couleurs et le centre se voit attribuer la quatrième couleur.

Il est possible de compter les colorations distinctes d'un graphe. Cela donne une fonction dépendant du nombre de couleurs autorisé. Cette fonction est polynomiale et est qualifiée de polynôme chromatique du graphe. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs à au nombre chromatique du graphe et est de degrés n. Il est égal à :

$P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n(x-2)})$

