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