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 verse como un refinamiento de la coloración habitual de los gráficos . El número cromático circular de un gráfico , denotado, puede venir dado por cualquiera de las siguientes definiciones, todas las cuales son equivalentes (para gráficos finitos). ${\displaystyle G}$ ${\displaystyle \chi _{c}(G)}$

1. ${\displaystyle \chi _{c}(G)}$es el mínimo sobre todos los números reales , de modo que existe un mapa desde a un círculo de circunferencia 1 con la propiedad de que dos vértices adyacentes cualesquiera 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 mínimo sobre todos los números racionales para que exista una aplicación del grupo cíclico con la propiedad de que los vértices adyacentes se asignan a elementos separados por una distancia. ${\displaystyle {\tfrac {n}{k}}}$ ${\displaystyle V(G)}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \geq k}$
3. En un gráfico orientado, declare el desequilibrio de un ciclo dividiéndolo 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. Defina el desequilibrio del gráfico orientado como el desequilibrio máximo de un ciclo. Ahora bien, 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 consideramos 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 de estrellas".

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

Gráficos circulares completos.

Para números enteros tales que , el gráfico circular completo (también conocido como camarilla circular ) es el gráfico con un conjunto de vértices y bordes entre elementos a 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 solo 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 gráfico circular completo. El hecho crucial de estos gráficos es que admiten 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 del homomorfismo entre ellos refina el orden dado por gráficos 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 equivalente

${\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 de la flor snark J ₅ a K _5/2 ≈ C ₅ , que viene antes de corresponder al hecho de que ${\displaystyle K_{3}}$ ${\displaystyle \chi _{c}(J_{5})\leq 2.5<3.}$

Ver también

• Coloración de rango

Referencias

• Nadolski, Adam (2004), "Coloración circular de gráficos", Coloración de gráficos , Contemp. Matemáticas, vol. 352, Providencia, Rhode Island: Amer. Matemáticas. Soc., págs. 123–137, doi :10.1090/conm/352/09, ISBN 978-0-8218-3458-9, señor  2076994.
• Vince, A. (1988), "Número cromático de estrellas", Journal of Graph Theory , 12 (4): 551–559, doi :10.1002/jgt.3190120411, SEÑOR  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.