- Graphe de Golomb
-
Graphe de Golomb Nombre de sommets 10 Nombre d'arêtes 18 Distribution des degrés 3 (6 sommets)
4 (3 sommets)
6 (1 sommet)Rayon 2 Maille 3 Automorphismes 6 Nombre chromatique 4 Indice chromatique 6 Propriétés Distance-unité
Hamiltonien
Planairemodifier 
Le graphe de Golomb est, en théorie des graphes, un graphe possédant 10 sommets et 18 arêtes. Il fut découvert par Golomb entre 1960 et 1965[1].
Sommaire
Propriétés
Propriétés générales
Il est possible de tracer le graphe de Golomb sur un plan sans qu'aucune de ses arêtes se croisent. Le graphe de Golomb est donc planaire. C'est également un graphe distance-unité : il peut s'obtenant à partir d'une collection de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1.
Coloriage
Le nombre chromatique du graphe de Golomb est 4. C'est-à-dire qu'il est possible de le colorer avec 4 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.
Le problème de Hadwiger–Nelson, introduit en 1944 par Hugo Hadwiger et Edward Nelson, concerne le nombre minimal de couleur qu'il faut pour colorier le plan de façons à ce que deux points à une distance de 1 ne soient jamais de la même couleur[2]. Il peut être formalisé en théorie des graphes de la façon suivante : quel est le nombre chromatique maximal d'un graphe distance-unité ? Le problème est toujours ouvert mais le graphe de Golomb, avec son nombre chromatique égal à 4, fournit une borne inférieure, la meilleure connue à ce jour. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser[3].
L'indice chromatique du graphe de Golomb est 6. Il existe donc une 6-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
Propriétés algébriques
Le groupe d'automorphismes du graphe de Golomb est un groupe d'ordre 6 isomorphe au groupe diédral D3, le groupe des isométries du plan conservant un triangle isocèle. Ce groupe est constitué de 3 éléments correspondant aux rotations et de 3 autres correspondant aux réflexions.
Le polynôme caractéristique du graphe de Golomb est : (x3 + x2 − 2x − 1)2(x4 − 2x3 − 11x2 + 8x + 27).
Voir aussi
Liens internes
Liens externes
- (en) Eric W. Weisstein, Golomb Graph (MathWorld)
Références
- (en) Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators New York: Springer, pp. 19-20, 2008.
- (en) O'Rourke, Joseph, « Problem 57: Chromatic Number of the Plane » sur The Open Problems Project.
- (en) Moser, L. and Moser, W. «Problem 10.» Canad. Math. Bull. 4, 187-189, 1961.
Catégorie :- Graphe remarquable
Wikimedia Foundation. 2010.
