Graphe de Golomb

Graphe de Golomb
Image illustrative de l’article 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 Consultez la documentation du modèle

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

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'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

Le graphe de Golomb est distance-unité et nécessite 4 couleurs pour colorer ses sommets.

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

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 : ( x 3 + x 2 − 2 x − 1 ) 2 ( x 4 − 2 x 3 − 11 x 2 + 8 x + 27 ) {\displaystyle (x^{3}+x^{2}-2x-1)^{2}(x^{4}-2x^{3}-11x^{2}+8x+27)} .

Notes et références

  1. ↑ (en) Alexander Soifer, The Mathematical Coloring Book, Springer, 2009, (ISBN 978-0-387-74640-1), p. 19
  2. ↑ (en) Joseph O'Rourke, « Problem 57: Chromatic Number of the Plane », sur The Open Problems Project
  3. ↑ (en) L. Moser et W. Moser, « Problem 10 », dans Canad. Math. Bull., n° 4, 1961, p. 187-189

Lien externe

(en) Eric W. Weisstein, « Golomb Graph », sur MathWorld

  • icône décorative Portail des mathématiques