Coloración circular

En teoría de grafos , la coloración circular es un tipo de coloración que puede considerarse un refinamiento de la coloración de grafos habitual . El número cromático circular de un grafo${\displaystyle G}$, denotado${\displaystyle \chi _{c}(G)}$puede estar dada por cualquiera de las siguientes definiciones, todas las cuales son equivalentes (para grafos finitos).

1. ${\displaystyle \chi _{c}(G)}$es el ínfimo sobre todos los números reales${\displaystyle r}$de modo que exista un mapa de${\displaystyle V(G)}$a un círculo de circunferencia 1 con la propiedad de que cualesquiera dos vértices adyacentes se mapean a puntos a distancia${\displaystyle \geq {\tfrac {1}{r}}}$a lo largo de este círculo.
2. ${\displaystyle \chi _{c}(G)}$es el ínfimo sobre todos los números racionales${\displaystyle {\tfrac {n}{k}}}$de modo que exista un mapa de${\displaystyle V(G)}$al grupo cíclico${\displaystyle \mathbb {Z} /n\mathbb {Z} }$con la propiedad de que los vértices adyacentes se asignan a elementos a distancia${\displaystyle \geq k}$aparte.
3. En un grafo orientado , declare el desequilibrio de un ciclo.${\displaystyle C}$ser${\displaystyle |E(C)|}$dividido por el mínimo entre el número de aristas dirigidas en sentido horario y el número de aristas dirigidas en sentido antihorario. Definimos el desequilibrio del grafo orientado como el desequilibrio máximo de un ciclo. Ahora,${\displaystyle \chi _{c}(G)}$es el desequilibrio mínimo de una orientación de${\displaystyle G}$.

Es relativamente fácil ver que${\displaystyle \chi _{c}(G)\leq \chi (G)}$(especialmente usando 1 o 2), pero de hecho${\displaystyle \lceil \chi _ {c}(G)\rceil =\chi (G)}$Es en este sentido que consideramos el número cromático circular como un refinamiento del número cromático usual.

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

La coloración es dual al tema de los flujos sin punto de origen ni destino y, de hecho, la coloración circular tiene una noción dual natural: los flujos circulares.

Para números enteros${\displaystyle n,k}$de tal manera que${\displaystyle n\geq 2k}$, el gráfico circular completo${\displaystyle K_{n/k}}$(también conocido como camarilla circular ) es el grafo con conjunto de vértices${\displaystyle \mathbb {Z} /n\mathbb {Z} =\{0,1,\ldots ,n-1\}}$y bordes entre elementos a distancia${\displaystyle \geq k.}$ Es decir, el vértice i es adyacente a:

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

${\displaystyle K_{n/1}}$es simplemente el grafo completo K _n , mientras que${\displaystyle K_{2n+1/n}}$es el gráfico cíclico${\displaystyle C_{2n+1}.}$

Una coloración circular es entonces, según la segunda definición anterior, un homomorfismo en un grafo circular completo. El hecho crucial sobre estos grafos es que${\displaystyle K_{a/b}}$admite un homomorfismo en${\displaystyle K_{c/d}}$si y solo si${\displaystyle {\tfrac {a}{b}}\leq {\tfrac {c}{d}}.}$Esto justifica la notación, ya que si${\displaystyle {\tfrac {a}{b}}={\tfrac {c}{d}}}$entonces${\displaystyle K_{a/b}}$y${\displaystyle K_{c/d}}$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 números racionales.${\displaystyle \geq 2}$. Por ejemplo

${\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 puede interpretarse como un homomorfismo del snark de flores J ₅ en K _5/2 ≈ C ₅ , que aparece antes que${\displaystyle K_{3}}$correspondiente al hecho de que${\displaystyle \chi _{c}(J_{5})\leq 2.5<3.}$

• Clasificación por color

• Nadolski, Adam (2004), "Coloración circular de grafos", Coloración de grafos , Contemp. Math., vol.  352, Providence, RI: Amer. Math. Soc., pp. 123–137 , doi : 10.1090/conm/352/09 , ISBN  978-0-8218-3458-9, MR 2076994 .
• Vince, A. (1988), "Número cromático estrellado", Journal of Graph Theory , 12 (4): 551– 559, doi : 10.1002/jgt.3190120411 , MR 0968751 .
• Zhu, X. (2001), "Número cromático circular, una revisión", Matemáticas Discretas , 229 ( 1–3 ): 371–410 , doi : 10.1016/S0012-365X(00)00217-X , MR 1815614 .