Graphe de Golomb

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.

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.

Le groupe d'automorphismes du graphe de Golomb est un groupe d'ordre 6 isomorphe au groupe diédral D₃, 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 : ${\displaystyle (x^{3}+x^{2}-2x-1)^{2}(x^{4}-2x^{3}-11x^{2}+8x+27)}$.