En teoría de grafos , el grafo de Golomb es un grafo 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 unidad de distancia que requiere cuatro colores en cualquier color de gráfico . Por lo tanto, como el eje 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 extremos de colores diferentes requiere al menos cuatro colores. [1]
Gráfico de Golomb | |
---|---|
![]() | |
Lleva el nombre de | Solomon W. Golomb |
Vértices | 10 |
Bordes | 18 |
Automorfismos | 6 |
Número cromático | 4 |
Propiedades | |
Tabla de gráficos y parámetros |
Construcción
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/f/fd/GolombGraphProperties.svg/220px-GolombGraphProperties.svg.png)
El método de construcción del gráfico de Golomb como un gráfico de unidad de distancia, mediante el dibujo de un polígono regular exterior conectado a un polígono interior retorcido o polígono en estrella, también se ha utilizado para representaciones de unidades de distancia del gráfico de Petersen y de los gráficos de Petersen generalizados . [2] Al igual que con el eje de Moser, las coordenadas de la incrustación de unidades de distancia del gráfico de Golomb se pueden representar en el campo cuadrático . [3]
Coloración fraccionada
El número cromático fraccionario del gráfico de Golomb es 10/3. El hecho de que este número sea al menos así de grande se deriva del hecho de que la gráfica 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 así de grande se deriva del hecho de que se pueden encontrar 10 conjuntos independientes de tres vértices, de modo que cada vértice se encuentra exactamente en tres de estos conjuntos. Este número cromático fraccionario es menor que el número 7/2 para el eje de Moser y menor que el número cromático fraccionario del gráfico de distancia unitaria del plano, que está acotado entre 3.6190 y 4.3599. [4]
Referencias
- ^ Soifer, Alexander (2008), El libro de colorear matemático: Matemáticas de colorear y la colorida vida de sus creadores , Nueva York: Springer, p. 19, ISBN 978-0-387-74640-1
- ^ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2012), "Todos los gráficos de Petersen generalizados son gráficos de unidad de distancia", Journal of the Korean Mathematical Society , 49 (3): 475–491, doi : 10.4134 / JKMS.2012.49.3.475 , MR 2953031
- ^ Pegg, Ed, Jr. (21 de diciembre de 2017), "Moser Spindles, Golomb Graphs y Root 33" , Wolfram Demonstrations Project
- ^ Cranston, Daniel W .; Rabern, Landon (2017), "El número cromático fraccional del plano", Combinatorica , 37 (5): 837–861, arXiv : 1501.01647 , doi : 10.1007 / s00493-016-3380-3 , MR 3737371