Juego de colorear gráficos

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

Juego de colorear vértices

El juego de colorear vértices fue introducido en 1981 por Brams ^[1] y redescubierto diez años después por Bodlaender. ^[2] 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 colorear (en la versión estándar, comienza Alice).
3. Si es imposible colorear correctamente 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, Alice gana.

El número cromático del juego de un gráfico , indicado por , es el número mínimo de colores necesarios para que Alice gane el juego de colorear vértices en . Trivialmente, para cada gráfico , tenemos , donde está el número cromático de y su grado máximo . ^[3] ${\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, ^[4] la complejidad computacional quedó como " un interesante problema abierto ". Recién en 2020 se demostró que el juego es PSPACE-Complete. ^[5]

Relación con otras nociones

Coloración acíclica. Cada gráfico con número cromático acíclico tiene . ^[6] ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle \chi _{g}(G)\leq k(k+1)}$

Juego de marcar. Para cada gráfico , ¿dónde está el número de color del juego ? Casi todos los límites superiores conocidos para el número cromático de gráficos del juego se obtienen a partir de los límites del número de color del juego. ${\displaystyle G}$ ${\displaystyle \chi _{g}(G)\leq col_{g}(G)}$ ${\displaystyle col_{g}(G)}$ ${\displaystyle G}$

Restricciones de ciclo en los bordes. Si cada arista de un gráfico pertenece como máximo a ciclos, entonces . ^[7] ${\displaystyle G}$ ${\displaystyle c}$ ${\displaystyle \chi _{g}(G)\leq 4+c}$

Clases de gráficos

Para una clase de gráficas, denotamos por el entero más pequeño tal que cada gráfica de tiene . En otras palabras, es el límite superior exacto para el número cromático de gráficos del juego en esta clase. Este valor es conocido para varias clases de gráficos estándar y está limitado 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 : . ^[8] Se conocen criterios simples para determinar el número cromático de juego de un bosque sin vértice de grado 3. ^[9] Parece difícil determinar el número cromático de juego de bosques con vértices de grado 3, incluso para bosques con grado máximo 3. ${\displaystyle \chi _{g}({\mathcal {F}})=4}$
• Cactos : . ^[10] ${\displaystyle \chi _{g}({\mathcal {C}})=5}$
• Gráficos planos exteriores : . ^[11] ${\displaystyle 6\leq \chi _{g}({\mathcal {O}})\leq 7}$
• Gráficos planos : . ^[12] ${\displaystyle 7\leq \chi _{g}({\mathcal {P}})\leq 17}$
• Gráficas planas de circunferencia dada : , ^[13] , , . ^[14] ${\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: . ^[15] ${\displaystyle \chi _{g}({{\mathcal {T}}G})=5}$
• Árboles k parciales : . ^[dieciséis] ${\displaystyle \chi _{g}({\mathcal {T}}_{k})\leq 3k+2}$
• Gráficos de intervalos : , donde es para un gráfico el tamaño de su camarilla más grande . ^[17] ${\displaystyle 2\omega \leq \chi _{g}({\mathcal {I}})\leq 3\omega -2}$ ${\displaystyle \omega }$

Productos cartesianos. El número cromático del juego del producto cartesiano no está limitado por una función de y . En particular, el número cromático del juego de cualquier gráfico bipartito completo es igual a 3, pero no existe un límite superior para arbitrario . ^[18] Por otro lado, el número cromático del juego de está acotado arriba por una función de y . En particular, si y son ambos como máximo , entonces . ^[19] ${\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 una sola arista tenemos: ^[18]

${\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: ^[20]

${\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 ^[20] ${\displaystyle \chi _{g}(P_{2}\square W_{n})=5}$ ${\displaystyle n\geq 9.}$
• Grafos bipartitos completos : si ^[20] ${\displaystyle \chi _{g}(P_{2}\square K_{m,n})=5}$ ${\displaystyle m,n\geq 5.}$

Problemas abiertos

Estas preguntas siguen abiertas hasta la fecha.

Más colores para Alice ^[21]

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

Relaciones con otras nociones ^[21]

• Supongamos que una clase monótona de gráficos (es decir, una clase de gráficos cerrada por subgrafos) tiene un número cromático de juego acotado . ¿Es cierto que esta clase de gráfico tiene un número de color de juego limitado  ?
• Supongamos que una clase monótona de gráficos (es decir, una clase de gráficos cerrada por subgrafos) tiene un número cromático de juego acotado . ¿Es cierto que esta clase de gráfico tiene arboricidad limitada  ?
• ¿Es cierto que una clase monótona de gráficos de número cromático de juego acotado tiene un número cromático acíclico acotado  ?

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

• Conjetura: 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 gráficas tal que para cualquiera , existe tal que y . ¿ En qué familias de grafos se encuentran  ? ${\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 ^[18]

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

Juego de colorear bordes

El juego de colorear bordes , presentado por Lam, Shiu y Zu, ^[22] es similar al juego de colorear vértices, excepto que Alice y Bob construyen un color de borde adecuado en lugar de un color de vértice 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 colorear (en la versión estándar, comienza Alice).
3. Si es imposible colorear correctamente un borde e (para cualquier color, e es adyacente a un borde coloreado con él), entonces Bob gana.
4. Si el gráfico tiene todos los bordes coloreados, entonces Alice gana.

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

Caso general

Para cada gráfica G , . Hay gráficos que alcanzan estos límites, pero todos los gráficos que conocemos que alcanzan este límite superior tienen un grado máximo pequeño. ^[22] Existen gráficos con valores arbitrarios grandes de . ^[23] ${\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 tal que, para cualquier gráfico arbitrario , tenemos . ${\displaystyle \epsilon >0}$ ${\displaystyle G}$ ${\displaystyle \chi '_{g}(G)\leq (2-\epsilon )\Delta (G)}$
Esta conjetura es cierta cuando es lo suficientemente grande en comparación con el número de vértices en . ^[23] ${\displaystyle \Delta (G)}$ ${\displaystyle G}$

• Arboricidad. Sea la arboricidad de un gráfico . Cada gráfico con grado máximo tiene . ^[24] ${\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 gráficas, denotamos por el entero más pequeño tal que cada gráfica de tiene . En otras palabras, es el límite superior exacto para el índice cromático del juego de gráficos en esta clase. Este valor es conocido para varias clases de gráficos estándar y está limitado 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 . ^[22] ${\displaystyle \chi '_{g}(W_{3})=5}$ ${\displaystyle \chi '_{g}(W_{n})=n+1}$ ${\displaystyle n\geq 4}$
• Bosques  : cuándo y . ^[25] Además, si cada árbol de un bosque de se obtiene por subdivisión de un árbol oruga o no contiene dos vértices adyacentes con grado 4, entonces . ^[26] ${\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 gráfico  ? Si es verdad, ¿es suficiente? ^[22] ${\displaystyle c\geq 2}$ ${\displaystyle \chi '_{g}(G)\leq \Delta (G)+c}$ ${\displaystyle G}$ ${\displaystyle c=2}$

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

Juego de colorear de incidencia

El juego de colorear de incidencia es un juego de colorear de gráficos, introducido por Andrés, ^[27] y similar al juego de colorear de vértices, excepto que Alice y Bob construyen un color de incidencia adecuado en lugar de un color de vértice adecuado. 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 correctamente una incidencia sin color (en la versión estándar, comienza Alice).
3. Si es imposible colorear correctamente una incidencia i (para cualquier color, i es adyacente a una incidencia coloreada con él), entonces Bob gana.
4. Si todas las incidencias están coloreadas correctamente, Alice gana.

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

Para cada gráfico con grado máximo , tenemos . ^[27] ${\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 los bordes de un gráficose pueden dividir en dos conjuntos, uno de ellos induciendo un gráfico conarboricidady el segundo induciendo un gráfico con grado máximo, entonces. ^[28]Si además, entonces. ^[28] ${\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 gráfico k -degenerado con grado máximo , entonces . Además, cuándo y cuándo . ^[27] ${\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áficas, denotamos por el entero más pequeño tal que cada gráfica de tiene . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle i_{g}({\mathcal {C}})}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle i_{g}(G)\leq k}$

• Rutas  : Para , . ${\displaystyle k\geq 13}$ ${\displaystyle i_{g}(P_{k})=5}$
• Ciclos  : Para , . ^[29] ${\displaystyle k\geq 3}$ ${\displaystyle i_{g}(C_{k})=5}$
• Estrellas  : Para , . ^[27] ${\displaystyle k\geq 1}$ ${\displaystyle i_{g}(S_{2k})=3k}$
• Ruedas  : Para , . Para , . ^[27] ${\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 tener como subgrafo, entonces . ^[30] ${\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

• ¿El límite superior es ajustado para cada valor de  ? ^[27] ${\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 subgrafo de G )? ^[27]

Notas

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

Referencias (orden cronológico)

• Gardner, Martín (1981). "Juegos Matemáticos". Científico americano . vol. 23.
• Bodlaender, Hans L. (1991). "Sobre la complejidad de algunos juegos de colorear". Conceptos de teoría de grafos en informática . Apuntes de conferencias sobre 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.; Trotón, William T. (1993). "Sobre el número cromático del juego de algunas clases de gráficos" (PDF) . Ars Combinatoria . 35 (17): 143-150.
• Kierstead, Henry A.; Trotón, William T. (1994). "Colorear gráficos planos con un socio que no coopera" (PDF) . Revista de teoría de grafos . 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). "Juego de número cromático de gráficos planos exteriores". Revista de teoría de grafos . 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). "Juego de borde para colorear gráficos" (PDF) . Notas de teoría de grafos Nueva York . 37 : 17-19.
• Zhu, Xuding (1999). "El juego para colorear el número de gráficos planos". Revista de teoría combinatoria, serie B. 75 (2): 245–258. doi : 10.1006/jctb.1998.1878 .
• Kierstead, Henry A. (2000). "Un algoritmo de coloración de gráficos competitivo simple". Revista de teoría combinatoria, serie B. 78 (1): 57–68. doi : 10.1006/jctb.1999.1927 .
• Zhu, Xuding (2000). "El juego para colorear el número de k -árboles pseudo 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 del juego de k -Gráficos 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.
• Él, Wenjie; Hou, Xiaoling; Lih, Ko-Wei; Shao, Jiating; Wang, Weifan; Zhu, Xuding (2002). "Particiones de bordes de gráficos planos y sus números de coloración del juego". Revista de teoría de grafos . 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 .
• Andrés, Stephan D. (2006). "El índice cromático del juego de bosques de grado máximo Δ  5". Matemática Aplicada Discreta . 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) . Mensual Matemático Estadounidense . 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". Apuntes Electrónicos en Matemática Discreta . 29 : 353–357. CiteSeerX  10.1.1.107.111 . doi :10.1016/j.endm.2007.07.060.
• Sidorowicz, Elżbieta (2007). "El juego de números cromáticos y el juego de colorear números de cactus". Cartas de procesamiento de información . 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 gráficos del juego". Gráficas y Combinatoria . 24 (2): 67–70. doi :10.1007/s00373-008-0774-z. S2CID  19373685.
• Beveridge, Andrés; Bohman, Tom; Friezeb, Alan; Pikhurko, Oleg (2008). "Índice cromático de gráficos del juego con determinadas restricciones de grados". Informática 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 marcar". Revista de teoría combinatoria, serie B. 98 (1): 1–18. doi : 10.1016/j.jctb.2007.04.004 .
• Andrés, Stefan D. (2009). "El número cromático del juego de incidencia". Matemática Aplicada Discreta . 157 (9): 1980–1987. doi : 10.1016/j.dam.2007.10.021 .
• Andrés, Stefan D. (2009). "Errata a: El número cromático del juego de incidencia". Matemática Aplicada Discreta . 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
• Raspaud, André; Wu, Jiaojiao (2009). "Juego de números cromáticos de rejillas toroidales". Cartas de procesamiento de información . 109 (21–22): 1183–1186. doi :10.1016/j.ipl.2009.08.001.
• Sia, Charmaine (2009). "El número cromático del juego de algunas familias de gráficos de productos cartesianos" (PDF) . AKCE Revista Internacional de Gráficos y Combinatoria . 6 (2): 315–327. Archivado desde el original (PDF) el 14 de noviembre de 2011 . Consultado el 16 de julio de 2014 .
• Junosza-Szaniawski, Konstanty; Rożej, Lukasz (2010). "Número cromático de gráficos del juego con número de ciclos acotado localmente". Cartas de procesamiento de 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ática Aplicada Discreta . 159 (8): 683–694. doi : 10.1016/j.dam.2010.01.001 .
• Charpentier, Clément; Sopeña, Éric (2013). "Juego de coloración de incidencia y arboricidad de gráficos". Algoritmos combinatorios . Apuntes de conferencias sobre informática. vol. 8288, págs. 106-114. arXiv : 1304.0166 . doi :10.1007/978-3-642-45278-9_10. ISBN 978-3-642-45277-2. S2CID  14707501.
• Chan, Wai H.; Nong, Ge (2014). "El índice cromático de juego de algunos árboles de grado máximo 4". Matemática Aplicada Discreta . 170 : 1–6. doi : 10.1016/j.dam.2014.01.003 .
• Sekigushi, Yosuke (2014). "El juego para colorear el número de gráficos planos con una circunferencia determinada". Matemáticas discretas . 300 : 11-16. doi :10.1016/j.disc.2014.04.011.
• Charpentier, Clément; Sopeña, Éric (2014). "El número cromático del juego de incidencia de (a, d) -gráficos descomponibles". Revista de algoritmos discretos . 31 : 14-25. doi :10.1016/j.jda.2014.10.001. S2CID  1102795.
• Dunn, Carlos; Larsen, Víctor; Lindke, Kira; Retter, Troya; Toci, Dustin (2014). "El juego del número cromático de árboles y bosques". arXiv : 1410.5223 [matemáticas.CO].
• Costa, Eurinardo; Pessoa, Víctor Lage; Soares, Ronan; Sampaio, Rudini (2020). "PSPACE: integridad de dos juegos de colorear gráficos". Informática Teórica . 824–825: 36–45. doi : 10.1016/j.tcs.2020.03.022. S2CID  218777459.
• Bradshaw, Peter (2021). "Colores de gráficos con subgrafos bicolores restringidos: II. El juego de colorear gráficos". Revista de teoría de grafos . 100 (2): 371–383. arXiv : 2008.13275 . doi :10.1002/jgt.22786. S2CID  221377336.