Coloración circular

En teoría de grafos , la coloración circular es un tipo de coloración que puede considerarse como un refinamiento de la coloración de grafos habitual . El número cromático circular de un grafo , denotado, puede darse mediante cualquiera de las siguientes definiciones, todas las cuales son equivalentes (para grafos finitos). ${\estilo de visualización G}$$Estilo de visualización: \chi_{c}(G)}$

1. $Estilo de visualización: \chi_{c}(G)}$es el ínfimo sobre todos los números reales de modo que existe una función de a un círculo de circunferencia 1 con la propiedad de que cualesquiera dos vértices adyacentes se asignan a puntos a distancia a lo largo de este círculo.${\estilo de visualización r}$${\displaystyle V(G)}$${\displaystyle \geq {\tfrac {1}{r}}}$
2. $Estilo de visualización: \chi_{c}(G)}$es el ínfimo sobre todos los números racionales de modo que existe una función desde al grupo cíclico con la propiedad de que los vértices adyacentes se asignan a elementos separados por distancia.${\displaystyle {\tfrac {n}{k}}}$${\displaystyle V(G)}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \geq k}$
3. En un grafo orientado, declara que el desequilibrio de un ciclo se divide por el mínimo del número de aristas dirigidas en el sentido de las agujas del reloj y el número de aristas dirigidas en el sentido contrario a las agujas del reloj. Define el desequilibrio del grafo orientado como el desequilibrio máximo de un ciclo. Ahora, es el desequilibrio mínimo de una orientación de .${\estilo de visualización C}$${\displaystyle |E(C)|}$$Estilo de visualización: \chi_{c}(G)}$${\estilo de visualización G}$

Es relativamente fácil ver eso (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. ${\displaystyle \chi_{c}(G)\leq \chi(G)}$${\displaystyle \lceil \chi _ {c}(G)\rceil =\chi (G)}$

La coloración circular fue definida originalmente por Vince (1988), quien la llamó "coloración estrella".

La coloración es dual respecto del tema de los flujos de ninguna parte-cero y, de hecho, la coloración circular tiene una noción dual natural: flujos circulares.

Para números enteros tales que , el grafo circular completo (también conocido como camarilla circular ) es el grafo con vértices y aristas entre elementos a una distancia Es decir, el vértice i es adyacente a: ${\estilo de visualización n,k}$${\estilo de visualización n\geq 2k}$ $Estilo de visualización K_{n/k}}$${\displaystyle \mathbb {Z} /n\mathbb {Z} =\{0,1,\ldots ,n-1\}}$${\displaystyle \geq k.}$

${\displaystyle i+k,i+k+1,\ldots ,i+nk{\bmod {n}}.}$

$Estilo de visualización K_{n/1}$es simplemente el gráfico completo K _n , mientras que es el gráfico del ciclo$Estilo de visualización K_{2n+1/n}}$ ${\displaystyle C_{2n+1}.}$

Una coloración circular es entonces, según la segunda definición anterior, un homomorfismo en un grafo completo circular. El hecho crucial acerca de estos grafos es que admite un homomorfismo en si y sólo si Esto justifica la notación, ya que si entonces y son homomórficamente equivalentes. Además, el orden de homomorfismo entre ellos refina el orden dado por los grafos completos en un orden denso , correspondiente a los números racionales . Por ejemplo $Estilo de visualización K_{a/b}$$Estilo de visualización K_{c/d}$${\displaystyle {\frac {a}{b}}\leq {\frac {c}{d}}.}$${\displaystyle {\frac {a}{b}}={\frac {c}{d}}}$$Estilo de visualización K_{a/b}$$Estilo de visualización K_{c/d}$${\displaystyle \geq 2}$

${\displaystyle K_{2/1}\a K_{7/3}\a K_{5/2}\a \cdots \a K_{3/1}\a K_{4/1}\a \cdots }$

o equivalentemente

${\displaystyle K_{2}\a C_{7}\a C_{5}\a \cdots \a K_{3}\a K_{4}\a \cdots }$

El ejemplo de la figura se puede interpretar como un homomorfismo del snark de la flor J ₅ en K _5/2 ≈ C ₅ , que viene antes que lo que corresponde al hecho de que$Estilo de visualización K3$${\displaystyle \chi_{c}(J_{5})\leq 2.5<3.}$

• Coloración de rangos

• Nadolski, Adam (2004), "Coloración circular de gráficos", Graph colorings , Contemp. Math., vol. 352, Providence, RI: Amer. Math. Soc., págs. 123–137, doi :10.1090/conm/352/09, ISBN 978-0-8218-3458-9, Sr.  2076994.
• Vince, A. (1988), "Número cromático de estrella", Journal of Graph Theory , 12 (4): 551–559, doi :10.1002/jgt.3190120411, MR  0968751.
• Zhu, X. (2001), "Número cromático circular, un estudio", Discrete Mathematics , 229 (1–3): 371–410, doi :10.1016/S0012-365X(00)00217-X, MR  1815614.