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.

Juego de colorear Vertex

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] ${\displaystyle G}$ ${\displaystyle \chi _{g}(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \chi (G)\leq \chi _{g}(G)\leq \Delta (G)+1}$ ${\displaystyle \chi (G)}$ ${\displaystyle 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]

Relación con otras nociones

Coloración acíclica. Todo grafo con número cromático acíclico tiene . ^[7] ${\displaystyle G}$ ${\displaystyle 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. ${\displaystyle G}$ ${\displaystyle \chi _{g}(G)\leq col_{g}(G)}$ ${\displaystyle col_{g}(G)}$ ${\displaystyle G}$

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

Clases de gráficos

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}})}$ ${\displaystyle k}$ ${\displaystyle 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}$ ${\displaystyle \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\square H}$ ${\displaystyle \chi _{g}(G)}$ ${\displaystyle \chi _{g}(H)}$ ${\displaystyle K_{n,n}}$ ${\displaystyle \chi _{g}(K_{n,n}\square K_{m,m})}$ ${\displaystyle n,m}$ ${\displaystyle G\square H}$ ${\displaystyle {\textrm {col}}_{g}(G)}$ ${\displaystyle {\textrm {col}}_{g}(H)}$ ${\displaystyle {\textrm {col}}_{g}(G)}$ ${\displaystyle {\textrm {col}}_{g}(H)}$ ${\displaystyle t}$ ${\displaystyle \chi _{g}(G\square 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.}$

Problemas abiertos

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

Más colores para Alice ^[22]

• Supongamos que Alicia tiene una estrategia ganadora para el juego de colorear vértices en un grafo G con k colores. ¿Tiene una para k+1 colores?
  Uno esperaría que la respuesta fuera "sí", ya que tener más colores parece una ventaja para Alicia. Sin embargo, no existe ninguna prueba de que esta afirmación sea verdadera.
• ¿Existe una función f tal que, si Alicia tiene una estrategia ganadora para el juego de colorear vértices en un grafo G con k colores, entonces Alicia tiene una estrategia ganadora en G con f(k)  ?
  Relajación de la pregunta anterior.

Relaciones con otras nociones ^[22]

• Supongamos que una clase monótona de grafos (es decir, una clase de grafos cerrados por subgrafos) tiene un número cromático de juego acotado . ¿Es cierto que esta clase de grafos tiene un número de coloración de juego acotado  ?
• Supongamos que una clase monótona de grafos (es decir, una clase de grafos cerrados por subgrafos) tiene un juego cromático acotado . ¿Es cierto que esta clase de grafo tiene arboricidad acotada  ?
• ¿Es cierto que una clase monótona de gráficos de número cromático de juego acotado tiene número cromático acíclico acotado  ?

Reducción del grado máximo ^[10]

• Conjetura: Si es un bosque, existe tal que y . ${\displaystyle F}$ ${\displaystyle F'\subseteq F}$ ${\displaystyle \Delta (F')\leq \chi _{g}(F)}$ ${\displaystyle \chi _{g}(F')=\chi _{g}(F)}$
• Sea la clase de grafos tales que para cualquier , existe tal que y . ¿Qué familias de grafos hay en  ? ${\displaystyle {\mathcal {G}}}$ ${\displaystyle G\in {\mathcal {G}}}$ ${\displaystyle G'\subseteq G}$ ${\displaystyle \Delta (G')\leq \chi _{g}(G)}$ ${\displaystyle \chi _{g}(G')=\chi _{g}(G)}$ ${\displaystyle {\mathcal {G}}}$

Hipercubos ^[19]

• ¿Es cierto que para cualquier hipercubo  ? Se sabe que es cierto para . ^[19] ${\displaystyle \chi _{g}(G)=n+1}$ ${\displaystyle Q_{n}}$
  ${\displaystyle n\leq 4}$

Juego de colorear bordes

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}$

Caso general

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}$

Clases de gráficos

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}$

Problemas abiertos

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]

Juego de colorear Incidencia

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}$

Relaciones con otras nociones

• (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}$

Clases de gráficos

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 }$

Problemas abiertos

• ¿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]

Notas

1. Gardner (1981)
2. Bartnicki y otros (2007)
3. Bodlaender (1991)
4. Con menos colores que el número cromático, no hay una coloración adecuada de G y, por lo tanto, Alicia no puede ganar. Con más colores que el grado máximo, siempre hay un color disponible para colorear un vértice y, por lo tanto, Alicia no puede perder.
5. Bodlaender (1991)
6. Costa, Pessoa, Soares, Sampaio (2020)
7. Dinski y Zhu (1999)
8. Junosza-Szaniawski y Rożej (2010)
9. Faigle et al. (1993), e implícito en Junosza-Szaniawski y Rożej (2010)
10. Dunn y otros (2014)
11. Sidorowicz (2007), e implícito en Junosza-Szaniawski y Rożej (2010)
12. Guan y Zhu (1999)
13. Límite superior de Zhu (2008), que mejora los límites anteriores de 33 de Kierstead y Trotter (1994), 30 implícito en Dinski y Zhu (1999), 19 en Zhu (1999) y 18 en Kierstead (2000). Límite inferior propuesto por Kierstead y Trotter (1994). Véase un estudio dedicado al número cromático de juegos de grafos planares en Bartnicki et al. (2007).
14. Sekigushi (2014)
15. Él y otros (2002)
16. Raspaud y Wu (2009)
17. Zhu (2000)
18. Faigle y otros (1993)
19. Peterin (2007)
20. Bradshaw (2021)
21. Sia (2009)
22. Zhu (1999)
23. Lam, Shiu y Xu (1999)
24. Beveridge y otros (2008)
25. Bartnicki y Grytczuk (2008), mejorando los resultados en gráficos k -degenerados en Cai y Zhu (2001)
26. Límite superior de Δ+2 por Lam, Shiu y Xu (1999), luego límite de Δ+1 por Erdös et al. (2004) para los casos Δ=3 y Δ≥6, y por Andres (2006) para el caso Δ=5.
27. Las condiciones en los bosques con Δ=4 se encuentran en Chan & Nong (2014)
28. Andrés (2009a), véase también fe de erratas en Andrés (2009b)
29. Charpentier & Sopena (2014), ampliando los resultados de Charpentier & Sopena (2013).
30. Kim (2011), mejorando un resultado similar para k ≥ 7 en Andrés (2009a) (ver también erratas en Andrés (2009b))
31. Kim (2011)

Referencias (orden cronológico)

• Gardner, Martin (1981). "Juegos matemáticos". Scientific American . Vol. 23.
• Bodlaender, Hans L. (1991). "Sobre la complejidad de algunos juegos de colorear". Graph-Theoretic Concepts in Computer Science (Conceptos de teoría de grafos en informática). Lecture Notes in Computer Science (Apuntes de clase en informática). Vol. 484. págs. 30–40. CiteSeerX  10.1.1.18.9992 . doi :10.1007/3-540-53832-1_29. ISBN. 978-3-540-53832-5.
• Faigle, Ulrich; Kern, Walter; Kierstead, Henry A.; Trotter, William T. (1993). "Sobre el juego del número cromático de algunas clases de grafos" (PDF) . Ars Combinatoria . 35 (17): 143–150.
• Kierstead, Henry A.; Trotter, William T. (1994). "Coloración de grafos planos con un compañero no cooperativo" (PDF) . Journal of Graph Theory . 18 (6): 564–584. doi :10.1002/jgt.3190180605.
• Dinski, Thomas; Zhu, Xuding (1999). "Un límite para el número cromático de gráficos del juego". Matemáticas discretas . 196 (1–3): 109–115. doi : 10.1016/s0012-365x(98)00197-6 .
• Guan, DJ; Zhu, Xuding (1999). "Número cromático de juego de grafos planos exteriores". Journal of Graph Theory . 30 (1): 67–70. doi :10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m.
• Lam, Peter CB; Shiu, Wai C.; Xu, Baogang (1999). "Coloración de gráficos mediante juegos de borde" (PDF) . Graph Theory Notes NY . 37 : 17–19.
• Zhu, Xuding (1999). "El juego de colorear números de grafos planares". Journal of Combinatorial Theory, Serie B . 75 (2): 245–258. doi : 10.1006/jctb.1998.1878 .
• Kierstead, Henry A. (2000). "Un algoritmo simple de coloración de grafos competitivos". Journal of Combinatorial Theory, Serie B . 78 (1): 57–68. doi : 10.1006/jctb.1999.1927 .
• Zhu, Xuding (2000). "El juego de coloración de números de pseudoárboles k parciales ". Matemáticas discretas . 215 (1–3): 245–262. doi :10.1016/s0012-365x(99)00237-x.
• Cai, Leizhen; Zhu, Xuding (2001). "Índice cromático de juego de gráficos k -degenerados". Revista de teoría de grafos . 36 (3): 144–155. doi :10.1002/1097-0118(200103)36:3<144::aid-jgt1002>3.0.co;2-f.
• He, Wenjie; Hou, Xiaoling; Lih, Ko-Wei; Shao, Jiating; Wang, Weifan; Zhu, Xuding (2002). "Particiones de aristas de grafos planares y sus números de coloración del juego". Journal of Graph Theory . 41 (4): 307–311. doi : 10.1002/jgt.10069 . S2CID  20929383.
• Erdös, Peter L.; Faigle, Ulrich; Hochstättler, Winfried; Kern, Walter (2004). "Nota sobre el índice cromático de árboles del juego". Informática Teórica . 313 (3): 371–376. doi : 10.1016/j.tcs.2002.10.002 .
• Andres, Stephan D. (2006). "El índice cromático de juego de bosques de grado máximo Δ ⩾ 5". Matemáticas Aplicadas Discretas . 154 (9): 1317–1323. doi :10.1016/j.dam.2005.05.031.
• Bartnicki, Tomasz; Grytczuk, Jaroslaw; Kierstead, HA; Zhu, Xuding (2007). "El juego de colorear mapas" (PDF) . American Mathematical Monthly . 114 (9): 793–803. doi :10.1080/00029890.2007.11920471. JSTOR  27642332. S2CID  15901267.
• Peterin, Iztok (2007). "Juego de números cromáticos de gráficos de productos cartesianos". Notas electrónicas en matemáticas discretas . 29 : 353–357. CiteSeerX  10.1.1.107.111 . doi :10.1016/j.endm.2007.07.060.
• Sidorowicz, Elżbieta (2007). "El juego del número cromático y el juego del número de coloración de los cactus". Information Processing Letters . 102 (4): 147–151. doi :10.1016/j.ipl.2006.12.003.
• Bartnicki, Tomasz; Grytczuk, Jarosław (2008). "Una nota sobre el índice cromático de juego de grafos". Graphs and Combinatorics . 24 (2): 67–70. doi :10.1007/s00373-008-0774-z. S2CID  19373685.
• Beveridge, Andrew; Bohman, Tom; Friezeb, Alan; Pikhurko, Oleg (2008). "Índice cromático de juego de grafos con restricciones dadas en grados". Ciencias de la Computación Teórica . 407 (1–3): 242–249. doi :10.1016/j.tcs.2008.05.026.
• Zhu, Xuding (2008). "Estrategia de activación refinada para el juego de marcado". Journal of Combinatorial Theory, Serie B . 98 (1): 1–18. doi : 10.1016/j.jctb.2007.04.004 .
• Andres, Stefan D. (2009). "El juego de incidencia del número cromático". Matemáticas Aplicadas Discretas . 157 (9): 1980–1987. doi : 10.1016/j.dam.2007.10.021 .
• Andres, Stefan D. (2009). "Fe de erratas de: El juego de incidencia de números cromáticos". Matemáticas Aplicadas Discretas . 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
• Raspaud, André; Wu, Jiaojiao (2009). "Juego de números cromáticos en cuadrículas toroidales". Information Processing Letters . 109 (21–22): 1183–1186. doi :10.1016/j.ipl.2009.08.001.
• Sia, Charmaine (2009). "El número cromático de juego de algunas familias de gráficos de productos cartesianos" (PDF) . AKCE International Journal of Graphs and Combinatorics . 6 (2): 315–327. Archivado desde el original (PDF) el 2011-11-14 . Consultado el 2014-07-16 .
• Junosza-Szaniawski, Konstanty; Rożej, Łukasz (2010). "Número cromático de juego de grafos con número de ciclos acotado localmente". Cartas de procesamiento de la información . 110 (17): 757–760. doi :10.1016/j.ipl.2010.06.004.
• Kim, John Y. (2011). "El juego de incidencia del número cromático de caminos y subgrafos de ruedas". Matemáticas Aplicadas Discretas . 159 (8): 683–694. doi : 10.1016/j.dam.2010.01.001 .
• Charpentier, Clément; Sopena, Éric (2013). "Juego de coloración de incidencia y arboricidad de grafos". Combinatorial Algorithms . Lecture Notes in Computer Science. Vol. 8288. págs. 106–114. arXiv : 1304.0166 . doi :10.1007/978-3-642-45278-9_10. ISBN 978-3-642-45277-2.S2CID14707501  .​
• Chan, Wai H.; Nong, Ge (2014). "El índice cromático de juego de algunos árboles de grado máximo 4". Matemáticas Aplicadas Discretas . 170 : 1–6. doi : 10.1016/j.dam.2014.01.003 .
• Sekigushi, Yosuke (2014). "El juego de colorear el número de grafos planares con una circunferencia dada". Matemáticas discretas . 300 : 11–16. doi :10.1016/j.disc.2014.04.011.
• Charpentier, Clément; Sopena, Éric (2014). "El juego de incidencia del número cromático de grafos (a,d) -descomponibles". Journal of Discrete Algorithms . 31 : 14–25. doi :10.1016/j.jda.2014.10.001. S2CID  1102795.
• Dunn, Charles; Larsen, Victor; Lindke, Kira; Retter, Troy; Toci, Dustin (2014). "El juego de números cromáticos de árboles y bosques". arXiv : 1410.5223 [math.CO].
• Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). "Completitud de PSPACE de dos juegos de coloración de gráficos". Ciencias de la Computación Teórica . 824–825: 36–45. doi :10.1016/j.tcs.2020.03.022. S2CID  218777459.
• Bradshaw, Peter (2021). «Coloración de grafos con subgrafos bicolores restringidos: II. El juego de coloración de grafos». Revista de teoría de grafos . 100 (2): 371–383. arXiv : 2008.13275 . doi :10.1002/jgt.22786. S2CID  221377336.