Graphe de Chvátal

Graphe de Chvátal
graphe de Chvátal
Chvatal graph.draw.svg
Le graphe de Chvátal
Nombre de sommets 12
Nombre d'arêtes 24
Distribution des degrés 4-régulier
Rayon 2
Diamètre 2
Maille 4
Automorphismes 8 (D4)
Nombre chromatique 4
Indice chromatique 4
Propriétés Régulier
Hamiltonien
Eulérien
modifier Consultez la documentation du modèle

Le graphe de Chvátal est, en théorie des graphes, un graphe 4-régulier possédant 12 sommets et 24 arêtes. Il doit son nom à Václav Chvátal qui le découvrit en 1970[1].

Le graphe de Chvátal est hamiltonien et sans triangle. Il joue un rôle clef dans l'article de Herbert Fleischner et Gert Sabidussi prouvant en 2002 que déterminer si un graphe hamiltonien sans triangle est 3-colorable est un problème NP-complet[2].

Le graphe de Chvátal sert d'illustration à la conjecture de Grünbaum qui stipule que pour tout m>1 et n>2 il existe un graphe n-régulier de nombre chromatique m et de maille au moins n[3]. Le résultat est trivial pour n=2 et m=2,3 mais pour m>3 seuls peu de graphes illustrant la conjecture sont connus.

Sommaire

Propriétés

Propriétés générales

Le graphe de Chvátal a 370 cycles hamiltoniens distincts et est eulérien.

Le diamètre du graphe de Chvátal, l'excentricité maximale de ses sommets, est 2, son rayon, l'excentricité minimale de ses sommets, est 2 et sa maille, la longueur de son plus court cycle, est 4. Il s'agit d'un graphe 4-sommet-connexe et d'un graphe 4-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 4 sommets ou de 4 arêtes.

Coloriage

Le nombre chromatique du graphe de Chvátal est 4. C'est-à-dire qu'il est possible de le colorer avec 4 couleurs de tel façon que deux sommets reliés par une arêtes soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 3-coloration valide du graphe.

L'indice chromatique du graphe de Chvátal est 4. Il existe donc une 4-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommets soient toujours de couleurs différentes. Ce nombre est minimal.

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 à 4 et est de degrés 12. Il est égal à : (x − 3)(x − 2)(x − 1)x(x8 − 18x7 + 157x6 − 861x5 + 3228x4 − 8423x3 + 14850x2 − 16080x + 8143).

Propriétés algébriques

Le groupe d'automorphismes du graphe de Chvátal est un groupe d'ordre 8 isomorphe au groupe diédral D4, le groupe des isométries du plan conservant un carré. Ce groupe est constitué de 4 éléments correspondant aux rotations et de 4 autres correspondant aux réflexions.

Le polynôme caractéristique du graphe de Chvátal est : (x − 4)(x − 1)4x2(x + 1)(x + 3)2(x2 + x − 4).

Galerie

  • Le graphe de Chvátal est hamiltonien

  • Le graphe de Chvátal admet une 4-coloration

  • Autre représentation du graphe de Chvátal

Voir aussi

Liens internes

Liens externes

Références

  1. ↑ (en) V. Chvátal, « The smallest triangle-free 4-chromatic 4-regular graph », dans Journal of Combinatorial Theory, vol. 9, no 1, 1970, p. 93–94 [lien DOI] 
  2. ↑ (en) Herbert Fleischner et Gert Sabidussi, « 3-colorability of 4-regular Hamiltonian graphs », dans Journal of Graph Theory, vol. 42, no 2, 2002, p. 125–140 [lien DOI] 
  3. ↑ (en) Grünbaum, B. "A Problem in Graph Coloring." Amer. Math. Monthly 77, 1088-1092, 1970

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Chvátal de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Graphe Hamiltonien — En théorie des graphes, un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être… …   Wikipédia en Français

  • Graphe hamiltonien — En théorie des graphes, un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être… …   Wikipédia en Français

  • Graphe de Hatzel — Nombre de sommets 57 Nombre d arêtes 88 Distribution des degrés 3 (52 sommets) 4 (5 sommets) Rayon 7 Diamètre 8 Maille 4 Automorphismes 8 Nombr …   Wikipédia en Français

  • Graphe de Sousselier — Représentation du graphe de Sousselier. Nombre de sommets 16 Nombre d arêtes 27 Distribution des degrés 3 (11 sommets) 4 (4 sommets) 5 (1 sommet) Rayon …   Wikipédia en Français

  • Graphe de Wiener-Araya — Représentation du graphe de Wiener Araya. Nombre de sommets 42 Nombre d arêtes 67 Distribution des degrés 3 (34 sommets) 4 (8 sommets) Maille …   Wikipédia en Français

  • Graphe hypohamiltonien — En théorie des graphes, un graphe est hypohamiltonien s il n a pas de cycle hamiltonien mais que la suppression de n importe quel sommet du graphe suffit à le rendre hamiltonien. Sommaire 1 Histoire 2 Planarité 3 Exemples …   Wikipédia en Français

  • Graphe parfait — Théorème des graphes parfaits Sommaire 1 Contexte 2 Théorèmes 3 Intérêt 4 Notes 5 Références …   Wikipédia en Français

  • Graphe planaire extérieur — Un graphe planaire extérieur maximal, muni d un 3 coloriage. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l anglais, outer planar) s il peut être dessiné dans… …   Wikipédia en Français

  • Coloration De Graphe — En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon qu aucun nœud du… …   Wikipédia en Français

  • Coloration de graphe — En théorie des graphes, colorer un graphe signifie attribuer une couleur à chacun de ses sommets de manière à ce que deux sommets reliés par une arête soient de couleur différente. Est souvent recherchée l utilisation d un nombre minimal de… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”