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 Planaire |
modifier ![]() |
Le graphe de Golomb est, en théorie des graphes, un graphe possédant 10 sommets et 18 arêtes.
Il a été découvert par le mathématicien Solomon W. Golomb, de l'Université de Californie du Sud, entre 1960 et 1965[1].
Propriétés[modifier | modifier le code]
Propriétés générales[modifier | modifier le code]
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'obtenir à 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.
Coloration[modifier | modifier le code]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/GolombGraphProperties.svg/220px-GolombGraphProperties.svg.png)
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 couleurs qu'il faut pour colorier le plan de façon 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 jusqu'en 2018. 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 telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
Propriétés algébriques[modifier | modifier le code]
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 de la matrice d'adjacence du graphe de Golomb est : .
Notes et références[modifier | modifier le code]
- (en) Alexander Soifer, The Mathematical Coloring Book, Springer, 2009, (ISBN 978-0-387-74640-1), p. 19
- (en) Joseph O'Rourke, « Problem 57: Chromatic Number of the Plane », sur The Open Problems Project
- (en) L. Moser et W. Moser, « Problem 10 », dans Canad. Math. Bull., n° 4, 1961, p. 187-189
Lien externe[modifier | modifier le code]
(en) Eric W. Weisstein, « Golomb Graph », sur MathWorld