Graphe distance-unité
En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'une collection de point du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette (en).
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[1]. 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[2]. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser[3].
[modifier] Exemples
- Tous les graphe cycle ;
- N'importe quel hypercube, donc le graphe hexaédrique et le graphe tesseract ;
- Le graphe de Petersen ainsi que celui de Moser, de Harborth et de Golomb ;
- Le graphe roue W7 (c'est le seul graphe roue à être distance-unité) ;
- Le graphe papillon, le graphe longhorn, le graphe diamant, le graphe taureau, le graphe griffe, le graphe criquet, le graphe poisson, le graphe fléchette, le graphe fourche, le graphe cerf-volant, le graphe croix et le graphe mite.
[modifier] Dénombrement
Paul Erdős posa le problème suivant en 1946 : étant donnés n points, comment estimer le nombre maximal de paires de points pouvant être à une distance de 1 sur le plan euclidien[4] ? En d'autres termes quel est la densité maximal d'un graphe distance-unité d'ordre n ?
L'hypercube fournit une borne inférieure sur le nombre de paires de points proportionnelle à 
.
[modifier] Références
- (en) Joseph O'Rourke, « Problem 57: Chromatic Number of the Plane » sur The Open Problems Project.
- (en) A. Soifer (en), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, New York, Springer, 2008, p. 19-20
- (en) L. Moser et W. Moser, « Problem 10 », dans Canad. Math. Bull., n° 4, 1961, p. 187-189
- (en) Paul Erdős, « On sets of distances of n points », dans Amer. Math. Monthly, vol. 53, 1946, p. 248–250 [lien DOI]
