En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe pouvant être représenté par un ensemble de points du plan euclidien en reliant par une arête uniquement des paires de points distants d'une unité ; s'il existe une représentation où toutes les paires de points à distance 1 sont reliées, on parle de graphe distance-unité strict.
Les arêtes peuvent se croiser, si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. Si une représentation est sans croisement entre les arêtes, toutes de longueur 1, alors le graphe est qualifié de graphe-allumettes.
Exemples Les graphes chaine, les graphes grille, les graphes cycle, les graphes étoile. Les graphes prisme, dont le graphe cube, et les graphes hypercube, dont le graphe tesseract.
Le graphe de Petersen ainsi que ceux de Moser, de Harborth et de Golomb. à 4 sommets : le graphe diamant, le graphe griffe, le graphe patte. à 5 sommets : le graphe papillon, le graphe taureau, le graphe criquet, le graphe fléchette, le graphe cerf-volant, le graphe fourche, le graphe maison, le graphe bannière. à 6 sommets : le graphe poisson, le graphe croix, le graphe mite. à 7 sommets : le graphe roue W7 (c'est le seul graphe roue à être distance-unité), le graphe longhorn.
Dénombrements
Classement par nombre de sommets Le nombre de graphes distance-unités connexes à sommets à isomorphisme près est donné par la . +12345611251351
Nombre maximal d'arêtes gauche|vignette|Le graphe roue W7 est un graphe distance-unité à 7 sommets ayant un maximum d'arêtes (12).Paul Erdős posa le problème suivant en 1946 : quel est le nombre maximal d'occurrences d'une distance donnée (pouvant être prise égale à 1) déterminée par points dans le plan ? En d'autres termes quel est le nombre maximal d'arêtes d'un graphe distance-unité à sommets ?
Les valeurs de sont connues jusqu'à () : 12345678910111213140135791214182023273033 Jusqu'à , les graphes correspondants peuvent être tracés dans le réseau hexagonal, mais ce n'est plus le cas ensuite.
Le graphe hypercube fournit un minorant de proportionnel à .
En considérant des points dans une grille carrée avec un espacement soigneusement choisi, Erdős a trouvé un meilleur minorant égal à : pour une constante , et a offert 500 $ pour une preuve montrant que le nombre peut également être majoré par une fonction de cette forme.
En mai 2026, cette conjecture a été réfutée avec l'aide d'une intelligence artificielle, en exhibant une famille infinie de configurations montrant que pour une infinité de , pour une constante .
Ce problème est très lié au théorème de Szemerédi-Trotter.
Application au nombre chromatique du plan 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.. En utilisant le théorème de De Bruijn-Erdős, 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 A. Soifer, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, New York, Springer, 2008, .. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser L. Moser et W. Moser, « Problem 10 », dans Canad. Math. Bull., , 1961, .. Cependant, en , des graphes de nombre chromatique 5 (comportant plusieurs milliers de sommets, le plus petit a 1581 sommets) ont été découverts par Aubrey de Grey et contrôlés par ordinateur Aubrey de Grey, The chromatic number of the plane is at least 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.
Références
Voir aussi
Graphe-allumettes
Catégorie:Famille de graphes