Juego de colorear gráficos

El juego de colorear grafos es un juego matemático relacionado con la teoría de grafos . Los problemas de juegos de colorear surgieron como versiones teóricas de juegos de los conocidos problemas de coloración de grafos . En un juego de colorear, dos jugadores utilizan un conjunto dado de colores para construir una coloración de un grafo , siguiendo reglas específicas según el juego que consideremos. Un jugador intenta completar con éxito la coloración del grafo, cuando el otro intenta evitar que lo consiga.

El juego de colorear vértices fue introducido en 1981 por Steven Brams como un juego de colorear mapas ^{[1] [2]} y redescubierto diez años después por Bodlaender. ^[3] Sus reglas son las siguientes:

1. Alice y Bob colorean los vértices de un gráfico G con un conjunto k de colores.
2. Alice y Bob se turnan para colorear correctamente un vértice sin color (en la versión estándar, comienza Alice).
3. Si es imposible colorear adecuadamente un vértice v (para cualquier color, v tiene un vecino coloreado con él), entonces Bob gana.
4. Si el gráfico está completamente coloreado, entonces Alicia gana.

El número cromático del juego de un grafo , denotado por , es el número mínimo de colores que necesita Alicia para ganar el juego de colorear vértices en . Trivialmente, para cada grafo , tenemos , donde es el número cromático de y su grado máximo . ^[4]${\estilo de visualización G}$$Estilo de visualización: {\displaystyle \chi_{g}(G)}$${\estilo de visualización G}$${\estilo de visualización G}$${\displaystyle \chi (G)\leq \chi _ {g}(G)\leq \Delta (G)+1}$${\displaystyle \chi (G)}$${\estilo de visualización G}$${\displaystyle \Delta (G)}$

En el artículo de Bodlaender de 1991, ^[5] la complejidad computacional se dejó como " un problema abierto interesante ". Recién en 2020 se demostró que el juego es PSPACE-Complete. ^[6]

Coloración acíclica. Todo grafo con número cromático acíclico tiene . ^[7]${\estilo de visualización G}$ ${\estilo de visualización k}$${\displaystyle \chi_{g}(G)\leq k(k+1)}$

Juego de marcado. Para cada gráfico , , donde es el número de coloración del juego de . Casi todos los límites superiores conocidos para el número cromático del juego de gráficos se obtienen a partir de los límites del número de coloración del juego. ${\estilo de visualización G}$${\displaystyle \chi_{g}(G)\leq col_{g}(G)}$$estilo de visualización col_{g}(G)}$${\estilo de visualización G}$

Restricciones de ciclos en las aristas. Si cada arista de un grafo pertenece a, como máximo , ciclos, entonces . ^[8]${\estilo de visualización G}$${\estilo de visualización c}$${\displaystyle \chi_{g}(G)\leq 4+c}$

Para una clase de grafos, denotamos por el entero más pequeño tal que cada grafo de tenga . En otras palabras, es el límite superior exacto para el número cromático del juego de grafos en esta clase. Este valor es conocido para varias clases de grafos estándar y está acotado para algunas otras: ${\displaystyle {\mathcal {C}}}$${\displaystyle \chi_{g}({\mathcal {C}})}$${\estilo de visualización k}$${\estilo de visualización G}$${\displaystyle {\mathcal {C}}}$${\displaystyle \chi_{g}(G)\leq k}$${\displaystyle \chi_{g}({\mathcal {C}})}$

• Bosques : . ^[9] Se conocen criterios simples para determinar el número cromático de juego de un bosque sin vértice de grado 3. ^[10] Parece difícil determinar el número cromático de juego de bosques con vértices de grado 3, incluso para bosques con máximo grado 3.${\displaystyle \chi_{g}({\mathcal {F}})=4}$
• Cactus : . ^[11]${\displaystyle \chi_{g}({\mathcal {C}})=5}$
• Grafos extraplanares : . ^[12]${\displaystyle 6\leq \chi _{g}({\mathcal {O}})\leq 7}$
• Grafos planares : . ^[13]${\displaystyle 7\leq \chi _{g}({\mathcal {P}})\leq 17}$
• Gráficas planares de circunferencia dada : , ^[14] , , . ^[15]${\displaystyle \chi_{g}({\mathcal {P}}_{4})\leq 13}$ ${\displaystyle \chi_{g}({\mathcal {P}}_{5})\leq 8}$${\displaystyle \chi_{g}({\mathcal {P}}_{6})\leq 6}$${\displaystyle \chi_{g}({\mathcal {P}}_{8})\leq 5}$
• Rejillas toroidales: . ^[16]${\displaystyle \chi _{g}({{\mathcal {T}}G})=5}$
• Árboles k parciales : . ^[17]${\displaystyle \chi_{g}({\mathcal {T}}_{k})\leq 3k+2}$
• Gráficos de intervalos : , donde es para un gráfico el tamaño de su grupo más grande . ^[18]${\displaystyle 2\omega \leq \chi _ {g}({\mathcal {I}})\leq 3\omega -2}$${\estilo de visualización \omega}$

Productos cartesianos. El número cromático de juego del producto cartesiano no está acotado por una función de y . En particular, el número cromático de juego de cualquier grafo bipartito completo es igual a 3, pero no hay límite superior para para cualquier . ^[19] Por otra parte, el número cromático de juego de está acotado por encima por una función de y . En particular, si y son ambos como máximo , entonces . ^[20]${\displaystyle G\cuadrado H}$$Estilo de visualización: {\displaystyle \chi_{g}(G)}$$Estilo de visualización: \chi_{g}(H)}$${\displaystyle K_{n,n}}$${\displaystyle \chi_{g}(K_{n,n}\square K_{m,m})}$${\estilo de visualización n,m}$${\displaystyle G\cuadrado H}$${\displaystyle {\textrm {col}}_{g}(G)}$${\displaystyle {\textrm {col}}_{g}(H)}$${\displaystyle {\textrm {col}}_{g}(G)}$${\displaystyle {\textrm {col}}_{g}(H)}$${\estilo de visualización t}$${\displaystyle \chi _{g}(G\cuadrado H)\leq t^{5}-t^{3}+t^{2}}$

• Para un solo borde tenemos: ^[19]

${\displaystyle {\begin{aligned}\chi _{g}(K_{2}\square P_{k})&={\begin{cases}2&k=1\\3&k=2,3\\4&k\geq 4\end{cases}}\\\chi _{g}(K_{2}\square C_{k})&=4&&k\geq 3\\\chi _{g}(K_{2}\square K_{k})&=k+1\end{aligned}}}$

• Para las estrellas tenemos: ^[21]

${\displaystyle {\begin{aligned}\chi _{g}(S_{m}\square P_{k})&={\begin{cases}2&k=1\\3&k=2\\4&k\geq 3\end{cases}}\\\chi _{g}(S_{m}\square C_{k})&=4&&k\geq 3\end{aligned}}}$

• Árboles :${\displaystyle \chi _{g}(T_{1}\square T_{2})\leq 12.}$
• Ruedas : si ^[21]${\displaystyle \chi _{g}(P_{2}\square W_{n})=5}$${\displaystyle n\geq 9.}$
• Grafos bipartitos completos : si ^[21]${\displaystyle \chi _{g}(P_{2}\square K_{m,n})=5}$${\displaystyle m,n\geq 5.}$

Estas preguntas siguen abiertas hasta el día de hoy.

El juego de colorear bordes , introducido por Lam, Shiu y Zu, ^[23] es similar al juego de colorear vértices, excepto que Alice y Bob construyen un coloreado de bordes adecuado en lugar de un coloreado de vértices adecuado. Sus reglas son las siguientes:

1. Alice y Bob están coloreando los bordes de un gráfico G con un conjunto k de colores.
2. Alice y Bob se turnan para colorear correctamente un borde sin color (en la versión estándar, comienza Alice).
3. Si es imposible colorear correctamente un borde e (para cualquier color, e está adyacente a un borde coloreado con él), entonces Bob gana.
4. Si el gráfico está completamente coloreado en los bordes, entonces Alicia gana.

Aunque este juego puede considerarse como un caso particular del juego de colorear vértices en grafos lineales , en la literatura científica se lo considera principalmente como un juego distinto. El índice cromático del juego de un grafo , denotado por , es el número mínimo de colores que necesita Alicia para ganar este juego en . ${\displaystyle G}$${\displaystyle \chi '_{g}(G)}$${\displaystyle G}$

Para cada grafo G , . Hay grafos que alcanzan estos límites pero todos los grafos que conocemos que alcanzan este límite superior tienen un grado máximo pequeño. ^[23] Existen grafos con para valores arbitrarios grandes de . ^[24]${\displaystyle \chi '(G)\leq \chi '_{g}(G)\leq 2\Delta (G)-1}$${\displaystyle \chi '_{g}(G)>1.008\Delta (G)}$${\displaystyle \Delta (G)}$

Conjetura. Existe una conjetura tal que, para cualquier grafo arbitrario , tenemos .${\displaystyle \epsilon >0}$${\displaystyle G}$${\displaystyle \chi '_{g}(G)\leq (2-\epsilon )\Delta (G)}$
Esta conjetura es verdadera cuando es suficientemente grande en comparación con el número de vértices en . ^[24]${\displaystyle \Delta (G)}$${\displaystyle G}$

• Arboricidad. Sea la arboricidad de un grafo . Todo grafo con grado máximo tiene . ^[25]${\displaystyle a(G)}$${\displaystyle G}$${\displaystyle G}$ ${\displaystyle \Delta (G)}$${\displaystyle \chi '_{g}(G)\leq \Delta (G)+3a(G)-1}$

Para una clase de grafos, denotamos por el entero más pequeño tal que cada grafo de tenga . En otras palabras, es el límite superior exacto para el índice cromático del juego de los grafos en esta clase. Este valor es conocido para varias clases de grafos estándar y está acotado para algunas otras: ${\displaystyle {\mathcal {C}}}$${\displaystyle \chi '_{g}({\mathcal {C}})}$${\displaystyle k}$${\displaystyle G}$${\displaystyle {\mathcal {C}}}$${\displaystyle \chi '_{g}(G)\leq k}$${\displaystyle \chi '_{g}({\mathcal {C}})}$

• Ruedas : y cuando . ^[23]${\displaystyle \chi '_{g}(W_{3})=5}$${\displaystyle \chi '_{g}(W_{n})=n+1}$${\displaystyle n\geq 4}$
• Bosques  : cuando , y . ^[26] Además, si cada árbol de un bosque de se obtiene por subdivisión a partir de un árbol oruga o no contiene dos vértices adyacentes con grado 4, entonces . ^[27]${\displaystyle \chi '_{g}({\mathcal {F}}_{\Delta })\leq \Delta +1}$${\displaystyle \Delta \neq 4}$${\displaystyle 5\leq \chi '_{g}({\mathcal {F}}_{4})\leq 6}$
  ${\displaystyle F}$${\displaystyle {\mathcal {F}}_{4}}$${\displaystyle \chi '_{g}(F)\leq 5}$

Límite superior. ¿Existe una constante tal que para cada grafo  ? Si es cierto, ¿es suficiente ? ^[23]${\displaystyle c\geq 2}$${\displaystyle \chi '_{g}(G)\leq \Delta (G)+c}$${\displaystyle G}$${\displaystyle c=2}$

Conjetura sobre grados mínimos grandes. Hay un y un entero tales que cualquier gráfico con satisface . ${\displaystyle \epsilon >0}$${\displaystyle d_{0}}$${\displaystyle G}$${\displaystyle \delta (G)\geq d_{0}}$${\displaystyle \chi '_{g}(G)\geq (1+\epsilon )\delta (G)}$ ^[24]

El juego de coloración de incidencias es un juego de coloración de grafos, introducido por Andres, ^[28] y similar al juego de coloración de vértices, excepto que Alice y Bob construyen una coloración de incidencias adecuada en lugar de una coloración de vértices adecuada. Sus reglas son las siguientes:

1. Alice y Bob están coloreando las incidencias de un gráfico G con un conjunto k de colores.
2. Alice y Bob se turnan para colorear adecuadamente un incidente no coloreado (en la versión estándar, comienza Alice).
3. Si es imposible colorear adecuadamente una incidencia i (para cualquier color, i es adyacente a un incidente coloreado con él), entonces Bob gana.
4. Si todas las incidencias están coloreadas correctamente, entonces Alicia gana.

El número cromático del juego de incidencia de un gráfico , denotado por , es el número mínimo de colores que necesita Alicia para ganar este juego en . ${\displaystyle G}$${\displaystyle i_{g}(G)}$${\displaystyle G}$

Para cada gráfico con grado máximo , tenemos . ^[28]${\displaystyle G}$${\displaystyle \Delta }$${\displaystyle {\frac {3\Delta -1}{2}}<i_{g}(G)<3\Delta -1}$

• (a,d) -Descomposición .Este es el mejor límite superior que conocemos para el caso general. Si las aristas de un grafose pueden dividir en dos conjuntos, uno de ellos induciendo un grafo conarboricidad, el segundo induciendo un grafo con grado máximo, entonces.^[29]Si además, entonces.^[29]${\displaystyle G}$ ${\displaystyle a}$${\displaystyle d}$${\displaystyle i_{g}(G)\leq \left\lfloor {\frac {3\Delta (G)-a}{2}}\right\rfloor +8a+3d-1}$
  ${\displaystyle \Delta (G)\geq 5a+6d}$${\displaystyle i_{g}(G)\leq \left\lfloor {\frac {3\Delta (G)-a}{2}}\right\rfloor +8a+d-1}$
• Degeneración. Si es un grafo k -degenerado con grado máximo , entonces . Además, cuando y cuando . ^[28]${\displaystyle G}$ ${\displaystyle \Delta (G)}$${\displaystyle i_{g}(G)\leq 2\Delta (G)+4k-2}$${\displaystyle i_{g}(G)\leq 2\Delta (G)+3k-1}$${\displaystyle \Delta (G)\geq 5k-1}$${\displaystyle i_{g}(G)\leq \Delta (G)+8k-2}$${\displaystyle \Delta (G)\leq 5k-1}$

Para una clase de gráficos, denotamos por el entero más pequeño tal que cada gráfico de tiene . ${\displaystyle {\mathcal {C}}}$${\displaystyle i_{g}({\mathcal {C}})}$${\displaystyle k}$${\displaystyle G}$${\displaystyle {\mathcal {C}}}$${\displaystyle i_{g}(G)\leq k}$

• Caminos  : Para , .${\displaystyle k\geq 13}$${\displaystyle i_{g}(P_{k})=5}$
• Ciclos  : Para , . ^[30]${\displaystyle k\geq 3}$${\displaystyle i_{g}(C_{k})=5}$
• Estrellas  : Para , . ^[28]${\displaystyle k\geq 1}$${\displaystyle i_{g}(S_{2k})=3k}$
• Ruedas  : Para , . Para , . ^[28]${\displaystyle k\geq 6}$${\displaystyle i_{g}(W_{2k+1})=3k+2}$${\displaystyle k\geq 7}$${\displaystyle i_{g}(W_{2k})=3k}$
• Subgrafos de ruedas  : Para , si es un subgrafo de que tiene como subgrafo, entonces . ^[31]${\displaystyle k\geq 13}$${\displaystyle G}$${\displaystyle W_{k}}$${\displaystyle S_{k}}$${\displaystyle i_{g}(G)=\left\lceil {\frac {3k}{2}}\right\rceil }$

• ¿Es el límite superior estricto para cada valor de  ? ^[28]${\displaystyle i_{g}(G)<3\Delta (G)-1}$${\displaystyle \Delta (G)}$
• ¿Es el número cromático del juego de incidencia un parámetro monótono (es decir, es al menos tan grande para un gráfico G como para cualquier subgráfico de G )? ^[28]