En teoría de grafos , el gráfico de Golomb es un gráfico poliédrico con 10 vértices y 18 aristas . Lleva el nombre de Solomon W. Golomb , quien lo construyó (con una incrustación no plana ) como un gráfico de distancia unitaria que requiere cuatro colores en cualquier coloración del gráfico . 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 unitario tenga puntos finales de diferentes colores requiere al menos cuatro colores. [1]
El método de construcción del gráfico de Golomb como un gráfico de distancia unitaria, dibujando un polígono regular externo conectado a un polígono retorcido interno o un polígono en estrella, también se ha utilizado para representaciones de distancia unitaria del gráfico de Petersen y de los gráficos de Petersen generalizados . [2] Al igual que con el huso Moser, las coordenadas de la incrustación unidad-distancia del gráfico de Golomb se pueden representar en el campo cuadrático . [3]
El número cromático fraccionario del gráfico de Golomb es 10/3. El hecho de que este número sea al menos tan grande se deriva del hecho de que el gráfico 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 mucho tan grande se deriva del hecho de que se pueden encontrar 10 conjuntos independientes de tres vértices, de modo que cada vértice esté exactamente en tres de estos conjuntos. Este número cromático fraccionario es menor que el número 7/2 del huso Moser y menor que el número cromático fraccionario del gráfico de distancia unitaria del plano, que está limitado entre 3,6190 y 4,3599. [4]
![{\displaystyle \mathbb {Q} [{\sqrt {33}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b920b3da2daef8f7f2ff1cbc6618b2ad08963bd)