En théorie des graphes, le graphe roueWn est un graphe d'ordre formé en ajoutant un sommet « centre » connecté à tous les sommets du graphe cycleCn-1[1]. La notation Wn provient du nom anglais wheel graph mais n'est pas universelle. Certains auteurs préfèrent Wn-1, faisant référence à la longueur du cycle.
Propriétés générales
Pour les valeurs impaires de n, le graphe Wn est un graphe parfait. Quand n est pair et supérieur ou égal à 6, le graphe roue Wn n'est pas parfait.
Le nombre de cycles dans le graphe roue Wn est égal à (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 Wn est Wn lui-même, faisant du graphe roue un graphe autodual. Tout graphe planaire maximal autre que le graphe completK4 = W4, contient comme sous-graphe ou W5 ou W6.
Le graphe roue W6 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 W6 a un nombre de Ramsey égal à 17 alors que le graphe complet avec le même nombre chromatique, K4, a un nombre de Ramsey égal à 18[3]. En effet, pour tout graphe G d'ordre 17, G ou son complément contient un sous-graphe isomorphe à W6, alors que ni le graphe de Paley d'ordre 17 ni son complément ne contiennent un sous-graphe isomorphe à K4.
Coloration
Pour les valeurs impaires de n, le graphe Wn a un nombre chromatique de 3: les sommets du cycle Cn-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 Cn-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 à:
