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'un ensemble de points 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.

Le graphe de Petersen est un graphe distance-unité : il peut être tracé sur le plan avec des arêtes toutes de longueur 1.

L'hypercube Q₄ est un graphe distance-unité.

Exemples

• Tous les cycles et toutes les grilles ;
• 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 W₇ (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.

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 ? En d'autres termes quelle est la densité maximale d'un graphe distance-unité d'ordre n ? Ce problème est très lié au théorème de Szemerédi-Trotter.

L'hypercube fournit une borne inférieure sur le nombre de paires de points proportionnelle à n log n.

Application

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. 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. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser. Cependant, cette borne a été améliorée en 2018 grâce à la découverte d'un graphe distance-unité de nombre chromatique 5.

Généralisation

La notion de dimension d'un graphe reprend l'idée d'un graphe tracé avec des arêtes de longueur 1, mais ne se restreint pas au plan.