En teoría de grafos , el grafo de Golomb es un grafo poliédrico con 10 vértices y 18 aristas . Recibe su nombre de Solomon W. Golomb , quien lo construyó (con una incrustación no plana ) como un grafo de distancia unitaria que requiere cuatro colores en cualquier coloración del grafo . Por lo tanto, al igual que el huso de Moser más simple , proporciona un límite inferior para el problema de Hadwiger-Nelson : colorear los puntos del plano euclidiano de modo que cada segmento de línea unitaria tenga puntos finales de diferentes colores requiere al menos cuatro colores. [1]
El método de construcción del grafo de Golomb como un grafo de distancia unitaria, mediante el dibujo de un polígono regular exterior conectado a un polígono retorcido interior o polígono estrellado, también se ha utilizado para representaciones de distancia unitaria del grafo de Petersen y de grafos de Petersen generalizados . [2] Al igual que con el huso de Moser, las coordenadas de la incrustación de distancia unitaria del grafo de Golomb se pueden representar en el campo cuadrático . [3]
El número cromático fraccionario del grafo de Golomb es 10/3. El hecho de que este número sea al menos tan grande se deduce del hecho de que el grafo tiene 10 vértices, de los cuales como máximo tres pueden estar en cualquier conjunto independiente. El hecho de que el número sea como máximo tan grande se deduce del hecho de que se pueden encontrar 10 conjuntos independientes de tres vértices, de modo que cada vértice esté en exactamente tres de estos conjuntos. Este número cromático fraccionario es menor que el número 7/2 para el huso de Moser y menor que el número cromático fraccionario del grafo de distancia unitaria del plano, que está acotado entre 3,6190 y 4,3599. [4]
![{\displaystyle \mathbb {Q} [{\sqrt {33}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b920b3da2daef8f7f2ff1cbc6618b2ad08963bd)