Coloración circular

El número cromático de la flor snark J ₅ es 3, pero el número cromático circular es ≤ 5/2.

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). ${\displaystyle G}$ ${\displaystyle \chi _{c}(G)}$

1. ${\displaystyle \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. ${\displaystyle r}$ ${\displaystyle V(G)}$ ${\displaystyle \geq {\tfrac {1}{r}}}$
2. ${\displaystyle \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 . ${\displaystyle C}$ ${\displaystyle |E(C)|}$ ${\displaystyle \chi _{c}(G)}$ ${\displaystyle 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.

Grafos circulares completos

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: ${\displaystyle n,k}$ ${\displaystyle n\geq 2k}$ ${\displaystyle 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+n-k{\bmod {n}}.}$

${\displaystyle K_{n/1}}$es simplemente el gráfico completo K _n , mientras que es el gráfico del ciclo ${\displaystyle 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 ${\displaystyle K_{a/b}}$ ${\displaystyle K_{c/d}}$ ${\displaystyle {\tfrac {a}{b}}\leq {\tfrac {c}{d}}.}$ ${\displaystyle {\tfrac {a}{b}}={\tfrac {c}{d}}}$ ${\displaystyle K_{a/b}}$ ${\displaystyle K_{c/d}}$ ${\displaystyle \geq 2}$

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

o equivalentemente

${\displaystyle K_{2}\to C_{7}\to C_{5}\to \cdots \to K_{3}\to K_{4}\to \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 ${\displaystyle K_{3}}$ ${\displaystyle \chi _{c}(J_{5})\leq 2.5<3.}$

Véase también

• Coloración de rangos

Referencias

• 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.