Gra w kolorowanie wykresów

Kolorowanka wykresów to gra matematyczna związana z teorią grafów . Problemy z kolorowaniem gier powstały jako teoretyczne wersje dobrze znanych problemów z kolorowaniem grafów . W grze w kolorowanie dwóch graczy używa określonego zestawu kolorów do skonstruowania kolorowania wykresu , przestrzegając określonych zasad w zależności od gry, którą rozważamy. Jeden gracz próbuje pomyślnie zakończyć kolorowanie wykresu, podczas gdy drugi próbuje mu to uniemożliwić.

Gra w kolorowanie wierzchołków

Gra w kolorowanie wierzchołków została wprowadzona w 1981 roku przez Bramsa i ponownie odkryta dziesięć lat później przez Bodlaendera. Jego zasady są następujące:

1. Alicja i Bob kolorują wierzchołki grafu G zbiorem k kolorów.
2. Alicja i Bob na zmianę kolorują odpowiednio niepokolorowany wierzchołek (w wersji standardowej zaczyna Alicja).
3. nie można poprawnie pokolorować wierzchołka v (dla dowolnego koloru, v ma sąsiada pokolorowanego nim), wtedy wygrywa Bob.
4. Jeśli wykres jest całkowicie pokolorowany, Alicja wygrywa.

Liczba chromatyczna gry $\$ , oznaczona przez , to minimalna liczba kolorów potrzebnych Alicji do wygrania gry w kolorowanie wierzchołków $}$ na ${\ Displaystyle G}$ . , dla każdego $wykresu$ mamy ${\ Displaystyle \ chi (G) \ równoważnik \ chi _ {g} (G) \ równoważnik \ Delta (G) + 1} , gdzie jest liczbą$ chromatyczną χ ( sol $\ chi (G)}$${$ \ Displaystyle $stopień$ i .

W artykule Bodlaendera z 1991 roku złożoność obliczeniowa została pozostawiona jako „ interesujący otwarty problem ”. Dopiero w 2020 roku udowodniono, że gra jest PSPACE-Complete.

Związek z innymi pojęciami

Barwienie acykliczne. Każdy wykres $z$ acykliczną liczbą chromatyczną ma $\ Displaystyle \ chi _ {g} (G) \ równoważnik k (k +$$sol$ .

Gra w znakowanie. Dla każdego wykresu , gdzie ${\ Displaystyle col_ {g} (G)}$$\ Displaystyle G}$ , $\ Displaystyle \ chi _ {g} (G) \ równoważnik col_ {g} (G$ } to numer kolorowania gry ${\ displaystyle G}$ . Prawie każda znana górna granica liczby chromatycznej wykresów w grze jest uzyskiwana z granic liczby kolorowania gry.

Ograniczenia cyklu na krawędziach. Jeśli każda krawędź wykresu należy co najwyżej do $sol$ , to $c}$${\ Displaystyle \ chi _ {g} (G)$$\$ .

Klasy wykresów

Dla klasy $}}}$ oznaczamy liczbę całkowitą $displaystyle k}$$displaystyle \ chi _$$.$ \ taki, że każdy wykres $}$ ≤ $Displaystyle$$\$${g} (G)$ . Innymi słowy ${\ Displaystyle \ chi _ {g} ({\ mathcal {C}})}$ jest dokładną górną granicą chromatycznej liczby wykresów w tej klasie. Ta wartość jest znana dla kilku standardowych klas grafów i ograniczona dla niektórych innych:

• Lasy : ${\ Displaystyle \ chi _ {g} ({\ mathcal {F}}) = 4}$ . Znane są proste kryteria wyznaczania liczby chromatycznej gry lasu bez wierzchołka stopnia 3. Wyznaczenie liczby chromatycznej gry lasów o wierzchołkach stopnia 3 wydaje się trudne, nawet dla lasów o maksymalnym stopniu 3.
• kaktusy : ${\ Displaystyle \ chi _ {g} ({\ mathcal {C}}) = 5}$ .
• Wykresy płaszczyzny zewnętrznej : ${\ Displaystyle 6 \ równoważnik \ chi _ {g} ({\ mathcal {O}}) \ równoważnik 7}$ .
• Wykresy planarne : ${\ Displaystyle 7 \ równoważnik \ chi _ {g} ({\ mathcal {P}}) \ równoważnik 17}$ .
• Wykresy planarne danego obwodu : ${\ Displaystyle \ chi _ {g} ({\ mathcal {P}} _ {4}) \ równoważnik 13}$ , ${ \ Displaystyle \ chi _ {g} ({\ mathcal {P}} _ {5}) \ równoważnik 8}$ , ${\ Displaystyle \ chi _ {g} ({\ mathcal {P} }_{6})\równoważnik 6}$ , ${\ Displaystyle \ chi _ {g} ({\ mathcal {P}} _ {8}) \ równoważnik 5}$ .
• siatki toroidalne: ${\ Displaystyle \ chi _ {g} ({{\ mathcal {T}} G}) = 5}$ .
• Częściowe k -drzewa : ${\ Displaystyle \ chi _ {g} ({\ mathcal {T}} _ {k}) \ równoważnik 3k + 2}$ .
• ${\ Displaystyle 2 \ omega \ równoważnik \ chi _ {g} ({\ mathcal {I}}) \ równoważnik 3 \$ sol ) ${\ displaystyle \ omega}$ ω jest dla wykresu wielkości jego największej kliki .

Produkty kartezjańskie. Gra liczba chromatyczna iloczynu kartezjańskiego $sol$${\ Displaystyle \ chi _ {g} (G)$ funkcją i ${\ Displaystyle \ chi _ {g} (H)}$ . W szczególności liczba chromatyczna gry dowolnego pełnego wykresu dwudzielnego jest równa 3, ale nie ma górnej granicy dla ${\ Displaystyle K_ {n, n}}$${\ Displaystyle \ chi _ {g} (K_ {n, n} \ kwadrat K_ {m, m})}$ dla dowolnego ${\ Displaystyle n, m}$ . Z drugiej strony liczba chromatyczna gry ${$ ograniczona powyżej funkcją $} _ {g} (G) }$ i ${\ Displaystyle {\ textrm {col}} _ {g} (H)}$ . W szczególności, jeśli ${\ Displaystyle {\ textrm {col}} _ {g} (G)}$ i ${\ Displaystyle {\ textrm {col}} _ {g} (H) }$ oba są co najwyżej ${\ displaystyle t}$ , wtedy ${\ Displaystyle \ chi _ {g} (G \ kwadrat H) \ równoważnik t ^ {5} -t ^ {3} + t ^ {2}}$ .

• Dla pojedynczej krawędzi mamy:

${\ Displaystyle {\ rozpocząć {wyrównane} \ chi _ {g} (K_ {2} \ kwadrat P_ {k}) & = {\ rozpocząć {przypadki} 2 & k = 1 \\ 3 & k = 2,3 \\ 4 & k \geq 4\end{przypadki}}\\\chi _{g}(K_{2}\square C_{k})&=4&&k\geq 3\\\chi _{g}(K_{2}\square K_{k})&=k+1\end{aligned}}}$

• Dla gwiazd mamy:

${\ Displaystyle {\ rozpocząć {wyrównane} \ chi _ {g} (S_ {m} \ kwadrat P_ {k}) & = {\ rozpocząć {przypadki} 2 & k = 1 \\ 3 & k =2\\4&k\geq 3\end{przypadki}}\\\chi _{g}(S_{m}\kwadrat C_{k})&=4&&k\geq 3\end{wyrównane}}}$

• Drzewa : ${\ Displaystyle \ chi _ {g} (T_ {1} \ kwadrat T_ {2}) \ równoważnik 12.}$
• Koła : ${\ Displaystyle \ chi _ {g} (P_ {2} \ kwadrat W_ {n}) = 5},$ jeśli ${\ Displaystyle n \ geq 9. }$
• Kompletne wykresy dwudzielne : ${\ Displaystyle \ chi _ {g} (P_ {2} \ kwadrat K_ {m, n}) = 5}$ jeśli ${\ Displaystyle m, n \ geq 5.}$

Otwarte problemy

Te pytania są nadal otwarte do tej daty.

Więcej kolorów dla Alicji

• 
  Załóżmy, że Alicja ma zwycięską strategię w grze kolorowania wierzchołków na grafie G z k kolorami. Czy ona ma jeden dla k+1 kolorów? Można by oczekiwać odpowiedzi „tak”, ponieważ posiadanie większej liczby kolorów wydaje się zaletą dla Alicji. Jednak nie ma dowodów na to, że to stwierdzenie jest prawdziwe.
• 
  Czy istnieje funkcja f taka, że ​​jeśli Alicja ma zwycięską strategię w grze kolorowania wierzchołków na grafie G z k kolorami, to Alicja ma zwycięską strategię na G z f(k) ? Relaksacja poprzedniego pytania.

Relacje z innymi pojęciami

• Załóżmy, że monotoniczna klasa grafów (tj. klasa grafów zamkniętych podgrafami) ma ograniczoną liczbę chromatyczną gry . Czy to prawda, że ​​ta klasa grafów ma ograniczoną liczbę kolorów w grze ?
• Załóżmy, że monotoniczna klasa grafów (tj. klasa grafów zamkniętych podgrafami) ma ograniczoną liczbę chromatyczną gry . Czy to prawda, że ​​ta klasa grafów ma ograniczoną arboryczność ?
• Czy to prawda, że ​​monotoniczna klasa grafów ograniczonej liczby chromatycznej gier ma ograniczoną acykliczną liczbę chromatyczną ?

Zmniejszenie maksymalnego stopnia

• Przypuszczenie: Czy ${\ Displaystyle \ Delta (F') \ leq \ chi _ {g} (F)}$ lasem, istnieje taki, że istnieje $F'\ subseteq F}$$Displaystyle$ i ${\ Displaystyle \ chi _ {g} (F ') = \ chi _ {g} (F)}$ .
• Niech $będzie$ klasą wykresów taką, że dla każdego istnieje $\ in {\ mathcal {G}}}$${\ displaystyle G '\ subseteq G}$ takie, że ${\ Displaystyle \ Delta (G') \ równoważnik \ chi _ {g} (G)}$ i ${\ Displaystyle \ chi _ {g} (G ') = \ chi _ {g} (G)}$ . Jakie rodziny grafów są w ${\ displaystyle {\ mathcal {G}}}$ ?

hipersześciany

• 
  Czy to prawda, $​​dla$ hipersześcianu $}$ Q_ Wiadomo, że jest to prawdziwe dla ${\ Displaystyle n \ równoważnik 4}$ .

Gra w kolorowanie krawędzi

Gra w kolorowanie krawędzi , wprowadzona przez Lama, Shiu i Zu, jest podobna do gry w kolorowanie wierzchołków, z wyjątkiem tego, że Alicja i Bob konstruują odpowiednie kolorowanie krawędzi zamiast właściwego kolorowania wierzchołków. Jego zasady są następujące:

1. Alicja i Bob kolorują krawędzie wykresu G zestawem k kolorów.
2. Alicja i Bob na zmianę kolorują właściwie niepokolorowaną krawędź (w standardowej wersji zaczyna Alicja).
3. Jeśli krawędzi e nie da się odpowiednio pokolorować (dla dowolnego koloru e sąsiaduje z krawędzią nią pokolorowaną), to Bob wygrywa.
4. Jeśli wykres jest całkowicie pokolorowany krawędziami, Alicja wygrywa.

Chociaż tę grę można uznać za szczególny przypadek gry w kolorowanie wierzchołków na wykresach liniowych , w literaturze naukowej uważa się ją głównie za odrębną grę. Indeks chromatyczny gry $to$ , $oznaczony$ przez , Alicji do wygrania na ${\ Displaystyle G}$ .

Sprawa ogólna

Dla każdego wykresu sol , ${\ Displaystyle \ chi '(G) \ równoważnik \ chi '_ {g} (G) \ równoważnik 2 \ Delta (G)-1}$ . Istnieją grafy osiągające te granice, ale wszystkie znane nam grafy, które osiągają tę górną granicę, mają mały stopień maksymalny. Istnieją wykresy z ${\ Displaystyle \ chi '_ {g} (G)> 1,008 \ Delta (G)}$ dla dowolnych dużych wartości ${\ Displaystyle \ Delta (G)}$ .

Przypuszczenie. Istnieje ${\ displaystyle \ epsilon > 0}$$\ displaystyle \ chi '_ {g}(G)\leq (2-\epsilon )\Delta (G)}$ , że dla dowolnego dowolnego wykresu χ $)$ . To przypuszczenie jest prawdziwe, gdy ${\ Displaystyle \ Delta (G)}$ jest wystarczająco duży w porównaniu z liczbą wierzchołków w ${\ displaystyle G}$ .

• Arboryczność. Niech za $a (G)}$$Displaystyle$ będzie arborycznością wykresu . Każdy $wykres$ maksymalnym stopniu ma $)$${\ Displaystyle \ chi '_ {g} (G) \ równoważnik \ Delta (G) + 3a (G) -1}$ .

Klasy wykresów

Dla klasy $wykresów$ oznaczamy najmniejszą liczbę całkowitą do $})}$${\ displaystyle k}$ taki, że każdy wykres ma $χ$ sol $Displaystyle \ chi '_ {g} (G sol {\$$≤$ . Innymi słowy, ${\ Displaystyle \ chi '_ {g} ({\ mathcal {C}})}$ jest dokładną górną granicą indeksu chromatycznego wykresów w tej klasie. Ta wartość jest znana dla kilku standardowych klas grafów i ograniczona dla niektórych innych:

• Koła : ${\ Displaystyle \ chi '_ {g} (W_ {3}) = 5}$ i ${\ Displaystyle \ chi '_ { g} (W_ {n}) = n + 1}$ , gdy ${\ Displaystyle n \ geq 4}$ .
• 
  Lasy : ${\ Displaystyle \ chi '_ {g} ({\ mathcal {F}} _ {\ Delta}) \ równoważnik \ Delta +1},$ gdy ${\ displaystyle \ Delta \ neq 4}$ i ${\ Displaystyle 5 \ równoważnik \ chi '_ {g} ({\ mathcal {F}} _ {4}) \ równoważnik 6}$ . Co więcej, jeśli każde drzewo w lesie ${\ displaystyle F}$$_ '_ {g} (F) \ równoważnik 5}$ ( $Displaystyle$ 5 \ _ .

Otwarte problemy

Górna granica. Czy istnieje stała $)$ że $+ c}$$Displaystyle \ chi '_ {g} (G) \ równoważnik \ Delta (G$ dla każdego wykresu ${\ displaystyle G}$ ? Jeśli to $czy$ wystarczy

Hipoteza o dużych minimalnych stopniach. Istnieje $> 0}$$\ delta (G) \geq d_{0}}$$epsilon$ i liczba całkowita taka, że ​​dowolny wykres z $sol$ spełnia ${\ Displaystyle \ chi '_ {g} (G) \ geq (1+ \ epsilon) \ delta (G)}$ .

Gra w kolorowanie incydentów

Gra w kolorowanie częstości to gra w kolorowanie grafów, wprowadzona przez Andresa i podobna do gry w kolorowanie wierzchołków, z wyjątkiem tego, że Alicja i Bob konstruują właściwe kolorowanie częstości zamiast właściwego kolorowania wierzchołków. Jego zasady są następujące:

1. Alicja i Bob kolorują częstości występowania grafu G zbiorem k kolorów.
2. Alicja i Bob na zmianę odpowiednio kolorują bezbarwną instancję (w wersji standardowej zaczyna Alicja).
3. Jeśli incydentu i nie da się odpowiednio pokolorować (dla dowolnego koloru i sąsiaduje z incydentem pokolorowanym nim), to Bob wygrywa.
4. Jeśli wszystkie incydenty są odpowiednio pokolorowane, Alicja wygrywa.

Liczba chromatyczna gry występowania na $,$$oznaczona$ przez to liczba kolorów potrzebnych Alicji do wygrania ${ \displaystyle G}$ .

Dla każdego wykresu $o$ maksymalnym stopniu mamy $}{2}}<i_{g}(G)<3\Delta -1}$${$$\ Displaystyle {\ Frac {3 \$ .

Relacje z innymi pojęciami

• (a,d) -Rozkład . Jest to najlepsza górna granica, jaką znamy dla ogólnego przypadku. Jeśli krawędzie wykresu ${$$podzielić$ na dwa zestawy, jeden z nich indukuje wykres z , drugi indukuje wykres o maksymalnym stopniu, a $\ displaystyle a}$ za
  ${\ Displaystyle i_ {g} (G) \ równoważnik \ lewo \ lfloor {\ Frac {3 \ Delta (G) -a} {2}} \ prawo \ rfloor + 8a + 3d-1}$ . Jeśli ponadto ${\ Displaystyle \ Delta (G) \ geq 5a + 6d}$ , to ${\ Displaystyle i_ {g} (G) \ równoważnik \ lewo \ lfloor {\ Frac {3 \ Delta (G) -a} {2}} \ prawo \ rfloor + 8a + d-1}$ .
• Degeneracja. Jeśli jest $-$$_ i_ {g}(G)\równik 2\Delta (G)+4k-2}$ 2 wykresem maksymalnym stopniu , $≤$ . Co więcej, ${\ Displaystyle i_ {g} (G) \ równoważnik 2 \ Delta (G) + 3k-1},$ gdy ${\ Displaystyle \ Delta (G) \ geq 5k-1}$ i ja $\ Displaystyle i_ {g} (G) \ równoważnik \ Delta (G) + 8k-2},$ gdy ${\ Displaystyle \ Delta (G) \ równoważnik 5k-1}$ .

Klasy wykresów

Dla klasy wykresów oznaczamy przez najmniejszą liczbę całkowitą $k}$$} ({\ mathcal {C}}}}$$Displaystyle$$i_ {$ taki, że każdy wykres z do $\ displaystyle {\ mathcal {$$}}}$ ma ja ${\ Displaystyle i_ {g} (G) \ równoważnik k$ .

• Ścieżki : dla ${\ Displaystyle k \ geq 13}$ , ${\ Displaystyle i_ {g} (P_ {k}) = 5}$ .
• Cykle : dla ${\ Displaystyle k \ geq 3}$ , ${\ Displaystyle i_ {g} (C_ {k}) = 5}$ .
• Gwiazdy : dla ${\ Displaystyle k \ geq 1}$ , ${\ Displaystyle i_ {g} (S_ {2k}) = 3k}$ .
• Koła : dla ${\ Displaystyle k \ geq 6}$ , ${\ Displaystyle i_ {g} (W_ {2k + 1}) = 3k + 2}$ . k ${\ Displaystyle k \ geq 7}$ , $} (W_ {2k}) = 3k}$ .
• Podgrafy kół : Dla ${\ Displaystyle k \ geq 13}$$}$ jest podgrafem $geq 13$ jako W $Displaystyle K \$ podwykres, to ${\ Displaystyle i_ {g} (G) = \ lewo \ lceil {\ Frac {3k} {2}} \ prawo \ rceil}$ .

Otwarte problemy

• $sol$ górna dla $_ Delta (G)}$ ?
• Czy liczba chromatyczna gry o incydencie jest parametrem monotonicznym (tzn. czy jest co najmniej tak duża dla grafu G jak dla dowolnego podgrafu G )?

Referencje (porządek chronologiczny)

• Gardner, Martin (1981). „Gry matematyczne”. Naukowy Amerykanin . Tom. 23.
•    Bodlaender, Hans L. (1991). „O złożoności niektórych gier w kolorowanie”. Graf-teoretyczne koncepcje w informatyce . Notatki z wykładów z informatyki . Tom. 484. s. 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.; Kłusak, William T. (1993). „O grze Liczba chromatyczna niektórych klas wykresów” (PDF) . Ars Combinatoria . 35 (17): 143–150.
• Kierstead, Henry A.; Trotter, William T. (1994). „Kolorowanie wykresów planarnych z partnerem niechętnym do współpracy” (PDF) . Dziennik teorii grafów . 18 (6): 564–584. doi : 10.1002/jgt.3190180605 .
• Diński, Tomasz; Zhu, Xuding (1999). „Granica chromatycznej liczby wykresów w grze” . Matematyka dyskretna . 196 (1–3): 109–115. doi : 10.1016/s0012-365x(98)00197-6 .
• Guan, DJ; Zhu, Xuding (1999). „Gra chromatyczna liczba grafów zewnętrznych”. Dziennik teorii grafów . 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). „Kolorowanie wykresów w grze Edge” (PDF) . Notatki z teorii grafów NY . 37 : 17–19.
• Zhu, Xuding (1999). „Gra w kolorowanie liczby grafów planarnych” . Dziennik teorii kombinatorycznej, seria B. 75 (2): 245–258. doi : 10.1006/jctb.1998.1878 .
• Kierstead, Henry A. (2000). „Prosty algorytm kolorowania wykresów konkurencyjnych” . Dziennik teorii kombinatorycznej, seria B. 78 (1): 57–68. doi : 10.1006/jctb.1999.1927 .
• Zhu, Xuding (2000). „Gra kolorująca liczbę pseudo częściowych k -drzew” . Matematyka dyskretna . 215 (1–3): 245–262. doi : 10.1016/s0012-365x(99)00237-x .
• Cai, Leizhen; Zhu, Xuding (2001). „Indeks chromatyczny gry k -zdegenerowanych” . Dziennik teorii grafów . 36 (3): 144–155. doi : 10.1002/1097-0118(200103)36:3<144::aid-jgt1002>3.0.co;2-f .
•   On, Wenjie; Hou, Xiaoling; Lih, Ko-Wei; Shao, Jiating; Wang, Weifan; Zhu, Xuding (2002). „Podziały krawędziowe grafów planarnych i ich numery do kolorowania gier”. Dziennik teorii grafów . 41 (4): 307–311. doi : 10.1002/jgt.10069 . S2CID 20929383 .
• Erdös, Peter L.; Faigle, Ulrich; Hochstättler, Winfried; Kern, Walter (2004). „Uwaga na temat indeksu chromatycznego drzew” . Informatyka teoretyczna . 313 (3): 371–376. doi : 10.1016/j.tcs.2002.10.002 .
• Andres, Stephan D. (2006). „Wskaźnik chromatyczny gry lasów o maksymalnym stopniu Δ ⩾ 5” . Dyskretna matematyka stosowana . 154 (9): 1317–1323. doi : 10.1016/j.dam.2005.05.031 .
•    Bartnicki Tomasz; Grytczuk, Jarosław; Kierstead, Ha; Zhu, Xuding (2007). „Gra w kolorowanie map” (PDF) . Amerykański miesięcznik matematyczny . 114 (9): 793–803. doi : 10.1080/00029890.2007.11920471 . JSTOR 27642332 . S2CID 15901267 .
•   Peterin, Iztok (2007). „Gra chromatyczna liczba wykresów produktów kartezjańskich”. Notatki elektroniczne w matematyce dyskretnej . 29 : 353–357. CiteSeerX 10.1.1.107.111 . doi : 10.1016/j.endm.2007.07.060 .
• Sidorowicz, Elżbieta (2007). „Liczba chromatyczna gry i liczba kaktusów do kolorowania gry” . Listy dotyczące przetwarzania informacji . 102 (4): 147–151. doi : 10.1016/j.ipl.2006.12.003 .
•   Bartnicki Tomasz; Grytczuk, Jarosław (2008). „Uwaga na temat chromatycznego indeksu wykresów w grze”. Grafy i kombinatoryka . 24 (2): 67–70. doi : 10.1007/s00373-008-0774-z . S2CID 19373685 .
• Beveridge, Andrew; Bohman, Tom; Friezeb, Alan; Pichurko, Oleg (2008). „Indeks chromatyczny wykresów gier z podanymi ograniczeniami dotyczącymi stopni” . Informatyka teoretyczna . 407 (1–3): 242–249. doi : 10.1016/j.tcs.2008.05.026 .
• Zhu, Xuding (2008). „Udoskonalona strategia aktywacji gry znakowania” . Dziennik teorii kombinatorycznej, seria B. 98 (1): 1–18. doi : 10.1016/j.jctb.2007.04.004 .
• Andres, Stefan D. (2009). „Liczba chromatyczna gry o częstości występowania” . Dyskretna matematyka stosowana . 157 (9): 1980–1987. doi : 10.1016/j.dam.2007.10.021 .
• Andres, Stefan D. (2009). „Erratum to: Liczba chromatyczna gry o częstości występowania” . Dyskretna matematyka stosowana . 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
• Raspaud, Andrzej; Wu, Jiaojiao (2009). „Gra chromatyczna liczba siatek toroidalnych”. Listy dotyczące przetwarzania informacji . 109 (21–22): 1183–1186. doi : 10.1016/j.ipl.2009.08.001 .
• Sia, Charmaine (2009). „Gra chromatyczna liczba niektórych rodzin wykresów produktów kartezjańskich” (PDF) . AKCE International Journal of Graphs and Combinatoryics . 6 (2): 315–327. Zarchiwizowane od oryginału (PDF) w dniu 14.11.2011 . Źródło 2014-07-16 .
• Junosza-Szaniawski, Konstanty; Rożej, Łukasz (2010). „Gra chromatyczna liczba grafów z lokalnie ograniczoną liczbą cykli” . Listy dotyczące przetwarzania informacji . 110 (17): 757–760. doi : 10.1016/j.ipl.2010.06.004 .
• Kim, John Y. (2011). „Gra o częstość chromatyczną liczby ścieżek i podgrafów kół” . Dyskretna matematyka stosowana . 159 (8): 683–694. doi : 10.1016/j.dam.2010.01.001 .
•    Charpentier, Klemens; Sopena, Éric (2013). Gra w kolorowanie incydentów i arboryczność wykresów . Notatki z wykładów z informatyki . Tom. 8288. s. 106–114. ar Xiv : 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). „Indeks chromatyczny gry niektórych drzew o maksymalnym stopniu 4” . Dyskretna matematyka stosowana . 170 : 1–6. doi : 10.1016/j.dam.2014.01.003 .
• Sekigushi, Yosuke (2014). „Gra w kolorowanie liczby grafów planarnych o danym obwodzie” . Matematyka dyskretna . 300 : 11-16. doi : 10.1016/j.disc.2014.04.011 .
• Charpentier, Klemens; Sopena, Éric (2014). „Liczba chromatyczna gry częstości (a, d) -rozkładalnych grafów” . Dziennik algorytmów dyskretnych . 31 : 14–25. doi : 10.1016/j.jda.2014.10.001 .
• Dunn, Karol; Larsen, Victor; Lindke, Kira; Retter, Troja; Toci, Dustin (2014). „Gra liczba chromatyczna drzew i lasów”. arXiv : 1410,5223 [ matematyka.CO ].
•   Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). „PSPACE-kompletność dwóch gier do kolorowania wykresów” . Informatyka teoretyczna . 824-825: 36-45. doi : 10.1016/j.tcs.2020.03.022 . S2CID 218777459 .
•   Bradshaw, Peter (2021). „Kolorowanie wykresów z ograniczonymi dwukolorowymi podgrafami: II. Gra w kolorowanie wykresów”. Dziennik teorii grafów . 100 (2): 371–383. arXiv : 2008.13275 . doi : 10.1002/jgt.22786 . S2CID 221377336 .