En teoría de grafos , la coloración circular es un tipo de coloración que puede verse como un refinamiento de la coloración de grafos habitual . El número cromático circular de un gráfico, denotado se puede dar mediante cualquiera de las siguientes definiciones, todas las cuales son equivalentes (para gráficos finitos).
- es el mínimo sobre todos los números reales para que exista un mapa de a un círculo de circunferencia 1 con la propiedad de que dos vértices adyacentes se asignan a puntos a distancia a lo largo de este círculo.
- es el mínimo sobre todos los números racionales para que exista un mapa de al grupo cíclico con la propiedad de que los vértices adyacentes se asignan a elementos a distancia aparte.
- En un gráfico orientado, declare el desequilibrio de un ciclo ser - estar dividido por el mínimo del número de bordes dirigidos en sentido horario y el número de bordes dirigidos en sentido antihorario. Defina el desequilibrio del gráfico orientado como el desequilibrio máximo de un ciclo. Ahora, es el desequilibrio mínimo de una orientación de .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/ec/J5_circular_color.svg/300px-J5_circular_color.svg.png)
Es relativamente fácil ver que (especialmente usando 1 o 2), pero de hecho . Es en este sentido que vemos el número cromático circular como un refinamiento del número cromático habitual.
La coloración circular fue definida originalmente por Vince (1988) , quien la llamó "coloración de estrellas".
La coloración es dual con respecto al tema de los flujos cero en ninguna parte y, de hecho, la coloración circular tiene una noción dual natural: flujos circulares.
Gráficos circulares completos
Gráfico circular completo | |
---|---|
Vértices | norte |
Bordes | n ( n - 2 k + 1) / 2 |
Circunferencia | |
Número cromático | ⌈N / k⌉ |
Propiedades | ( N - 2 k + 1) -regular Vertex-transitivo circulant hamiltoniano |
Notación | |
Tabla de gráficos y parámetros |
Para enteros tal que , el gráfico circular completo (también conocida como camarilla circular ) es el gráfico con el conjunto de vértices y bordes entre elementos a distancia Ese es el vértice i adyacente a:
es solo el gráfico completo K n , mientras quees el gráfico del ciclo
Una coloración circular es entonces, de acuerdo con la segunda definición anterior, un homomorfismo en un gráfico circular completo. El hecho crucial sobre estos gráficos es que admite un homomorfismo en si y solo si Esto justifica la notación, ya que si luego y son homomórficamente equivalentes. Además, el orden de homomorfismo entre ellos refina el orden dado por gráficos completos en un orden denso , correspondiente a números racionales.. Por ejemplo
o equivalente
El ejemplo de la figura se puede interpretar como un homomorfismo de la flor snark J 5 en K 5/2 ≈ C 5 , que es anterior a correspondiente al hecho de que
Ver también
Referencias
- Nadolski, Adam (2004), "Coloración circular de gráficos", Coloración de gráficos , Contemp. Math., 352 , Providence, RI: Amer. Matemáticas. Soc., Págs. 123-137, doi : 10.1090 / conm / 352/09 , MR 2076994.
- Vince, A. (1988), "Star chromatic number", Journal of Graph Theory , 12 (4): 551–559, doi : 10.1002 / jgt.3190120411 , MR 0968751.
- Zhu, X. (2001), "Número cromático circular, una encuesta", Matemáticas discretas , 229 (1–3): 371–410, doi : 10.1016 / S0012-365X (00) 00217-X , MR 1815614.