Graf zbarvení hra - Graph coloring game

The graf zbarvení hra je matematická hra související s teorie grafů. Problémy s barvením hry vznikly jako herně teoretické verze známých zbarvení grafu problémy. Ve hře omalovánky dva hráči používají danou sadu barev k vytvoření zbarvení a graf, podle konkrétních pravidel v závislosti na hře, kterou zvažujeme. Jeden hráč se snaží úspěšně dokončit vybarvení grafu, když se druhý pokusí mu zabránit v jeho dosažení.

Vrchol zbarvení hra

The vrchol zbarvení hra byl představen v roce 1981 Bramsem^[1] a znovuobjeveno deset let poté Bodlaenderem.^[2] Jeho pravidla jsou následující:

Alice a Bob vybarvují vrcholy grafu G se sadou k barev.
Alice a Bob se střídají, správně zbarvení nezbarvený vrchol (ve standardní verzi začíná Alice).
Pokud vrchol proti není možné správně vybarvit (pro jakoukoli barvu proti má souseda barevného), pak vyhrává Bob.
Pokud je graf úplně zbarvený, vyhrává Alice.

The barevné číslo hry grafu ${ displaystyle G}$ , označeno ${ displaystyle chi _ {g} (G)}$ , je minimální počet barev potřebných k tomu, aby Alice vyhrála vrcholnou hru s barvami ${ displaystyle G}$ . Triviálně, pro každý graf ${ displaystyle G}$ , my máme ${ displaystyle chi (G) leq chi _ {g} (G) leq Delta (G) +1}$ , kde ${ displaystyle chi (G)}$ je chromatické číslo z ${ displaystyle G}$ a ${ displaystyle Delta (G)}$ jeho maximum stupeň.^[3]

Vztah k jiným pojmům

Acyklické zbarvení. Každý graf ${ displaystyle G}$ s acyklické chromatické číslo ${ displaystyle k}$ má ${ displaystyle chi _ {g} (G) leq k (k + 1)}$ .^[4]

Značkovací hra. Pro každý graf ${ displaystyle G}$ , ${ displaystyle chi _ {g} (G) leq col_ {g} (G)}$ , kde ${ displaystyle col_ {g} (G)}$ je hra zbarvení číslo z ${ displaystyle G}$ . Téměř každá známá horní hranice pro chromatický počet grafů hry se získává z hranic čísla zbarvení hry.

Omezení cyklu na hranách. Pokud každá hrana grafu ${ displaystyle G}$ patří nanejvýš ${ displaystyle c}$ cykly, pak ${ displaystyle chi _ {g} (G) leq 4 + c}$ .^[5]

Třídy grafů

Pro třídu ${ displaystyle { mathcal {C}}}$ grafů označujeme ${ displaystyle chi _ {g} ({ mathcal {C}})}$ nejmenší celé číslo ${ displaystyle k}$ tak, že každý graf ${ displaystyle G}$ z ${ displaystyle { mathcal {C}}}$ má ${ displaystyle chi _ {g} (G) leq k}$ . Jinými slovy, ${ displaystyle chi _ {g} ({ mathcal {C}})}$ je přesná horní mez pro chromatický počet grafů hry v této třídě. Tato hodnota je známá pro několik standardních tříd grafů a pro některé další omezená:

Lesy: ${ displaystyle chi _ {g} ({ mathcal {F}}) = 4}$ .^[6] Jsou známa jednoduchá kritéria pro určení barevného čísla hry lesa bez vrcholu stupně 3.^[7] Zdá se obtížné určit herní chromatický počet lesů s vrcholy stupně 3, a to i pro lesy s maximálním stupněm 3.
Kaktusy: ${ displaystyle chi _ {g} ({ mathcal {C}}) = 5}$ .^[8]
Vnější rovinné grafy: ${ displaystyle 6 leq chi _ {g} ({ mathcal {O}}) leq 7}$ .^[9]
Rovinné grafy: ${ displaystyle 7 leq chi _ {g} ({ mathcal {P}}) leq 17}$ .^[10]
Rovinné grafy daného obvod: ${ displaystyle chi _ {g} ({ mathcal {P}} _ {4}) leq 13}$ ,^[11] ${ displaystyle chi _ {g} ({ mathcal {P}} _ {5}) leq 8}$ , ${ displaystyle chi _ {g} ({ mathcal {P}} _ {6}) leq 6}$ , ${ displaystyle chi _ {g} ({ mathcal {P}} _ {8}) leq 5}$ .^[12]
Toroidní mřížky: ${ displaystyle chi _ {g} ({{ mathcal {T}} G}) = 5}$ .^[13]
Částečný k-stromy: ${ displaystyle chi _ {g} ({ mathcal {T}} _ {k}) leq 3k + 2}$ .^[14]
Intervalové grafy: ${ displaystyle 2 omega leq chi _ {g} ({ mathcal {I}}) leq 3 omega -2}$ , kde ${ displaystyle omega}$ je pro graf o velikosti největší klika.^[15]

Kartézské výrobky.Chromatické číslo hry kartézského produktu ${ displaystyle G čtverec H}$ není omezen funkcí ${ displaystyle chi _ {g} (G)}$ a ${ displaystyle chi _ {g} (H)}$ . Zejména herní chromatické číslo jakéhokoli úplného bipartitního grafu ${ displaystyle K_ {n, n}}$ se rovná 3, ale neexistuje žádná horní mez pro ${ displaystyle chi _ {g} (K_ {n, n} čtverec K_ {m, m})}$ pro libovolné ${ displaystyle n, m}$ .^[16]

Pro jednu hranu máme:^[16]

{ 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 {zarovnáno}}}

Pro hvězdy my máme:^[17]

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

Stromy: ${ displaystyle chi _ {g} (T_ {1} čtverec T_ {2}) leq 12.}$
Kola: ${ displaystyle chi _ {g} (P_ {2} čtverec W_ {n}) = 5}$ -li ${ displaystyle n geq 9.}$ ^[17]
Kompletní bipartitní grafy: ${ displaystyle chi _ {g} (P_ {2} čtverec K_ {m, n}) = 5}$ -li ${ displaystyle m, n geq 5.}$ ^[17]

Otevřené problémy

Tyto otázky jsou k tomuto datu stále otevřené.

Více barev pro Alici ^[18]

Předpokládejme, že Alice má vítěznou strategii pro hru omalování vrcholů v grafu G s k barvy. Má jeden pro k + 1 barvy?
Dalo by se očekávat, že odpovědi budou „ano“, protože mít více barev se zdá Alici výhodou. Neexistuje však žádný důkaz, že toto tvrzení je pravdivé.
Existuje nějaká funkce F takové, že pokud má Alice v grafu vítěznou strategii hry s barvením vrcholů G s k barvy, pak má Alice vítěznou strategii G s f (k) ?
Uvolnění předchozí otázky.

Vztahy s jinými pojmy ^[18]

Předpokládejme, že monotónní třída grafů (tj. Třída grafů uzavřená podgrafy) je ohraničená barevné číslo hry. Je pravda, že tato třída grafu je omezená hra zbarvení číslo ?
Předpokládejme, že monotónní třída grafů (tj. Třída grafů uzavřená podgrafy) je ohraničená barevné číslo hry. Je pravda, že tato třída grafu je omezená arboricita ?
Je pravda, že monotónní třída grafů ohraničené barevné číslo hry ohraničeno acyklické chromatické číslo ?

Snížení maximálního stupně ^[7]

Dohad: Je ${ displaystyle F}$ je les, existuje ${ displaystyle F ' subseteq F}$ takhle ${ displaystyle Delta (F ') leq chi _ {g} (F)}$ a ${ displaystyle chi _ {g} (F ') = chi _ {g} (F)}$ .
Nechat ${ displaystyle { mathcal {G}}}$ být třída grafů taková, že pro všechny ${ displaystyle G v { mathcal {G}}}$ , tady existuje ${ displaystyle G ' subseteq G}$ takhle ${ displaystyle Delta (G ') leq chi _ {g} (G)}$ a ${ displaystyle chi _ {g} (G ') = chi _ {g} (G)}$ . V čem jsou rodiny grafů ${ displaystyle { mathcal {G}}}$ ?

Hyperkrychle^[16]

Je to pravda? ${ displaystyle chi _ {g} (G) = n + 1}$ pro jakoukoli hyperkrychli ${ displaystyle Q_ {n}}$ ?
Je známo, že to platí pro ${ displaystyle n leq 4}$ .^[16]

Omalovánky hran

The hrana zbarvení hra, představili Lam, Shiu a Zu,^[19] je podobná hře na obarvení vrcholů, kromě toho, že Alice a Bob vytvoří vlastní zbarvení hran místo správného zbarvení vrcholů. Jeho pravidla jsou následující:

Alice a Bob zbarvují okraje grafem G se sadou k barev.
Alice a Bob se střídají, správně zbarvení nezbarvený okraj (ve standardní verzi začíná Alice).
Pokud hrana E není možné správně vybarvit (pro jakoukoli barvu E sousedí s hranou, která je ním zbarvena), pak vyhrává Bob.
Pokud je graf úplně zbarvený do okraje, vyhrává Alice.

I když tuto hru lze považovat za konkrétní případ vrchol zbarvení hra na spojnicové grafy, je ve vědecké literatuře považován hlavně za samostatnou hru. The herní chromatický index grafu ${ displaystyle G}$ , označeno ${ displaystyle chi '_ {g} (G)}$ , je minimální počet barev potřebných k tomu, aby Alice tuto hru vyhrála ${ displaystyle G}$ .

Obecný případ

Pro každý graf G, ${ displaystyle chi '(G) leq chi' _ {g} (G) leq 2 Delta (G) -1}$ . Existují grafy dosahující těchto hranic, ale všechny grafy, které známe, že dosahují této horní hranice, mají malý maximální stupeň.^[19] Existují grafy s ${ displaystyle chi '_ {g} (G)> 1,008 Delta (G)}$ pro libovolné velké hodnoty ${ displaystyle Delta (G)}$ .^[20]

Dohad. Tady je ${ displaystyle epsilon> 0}$ takový, že pro libovolný graf ${ displaystyle G}$ , my máme ${ displaystyle chi '_ {g} (G) leq (2- epsilon) Delta (G)}$ .
Tato domněnka je pravdivá, když ${ displaystyle Delta (G)}$ je dostatečně velký ve srovnání s počtem vrcholů v ${ displaystyle G}$ .^[20]

Arboricita. Nechat ${ displaystyle a (G)}$ být arboricita grafu ${ displaystyle G}$ . Každý graf ${ displaystyle G}$ s maximem stupeň ${ displaystyle Delta (G)}$ má ${ displaystyle chi '_ {g} (G) leq Delta (G) + 3a (G) -1}$ .^[21]

Třídy grafů

Pro třídu ${ displaystyle { mathcal {C}}}$ grafů označujeme ${ displaystyle chi '_ {g} ({ mathcal {C}})}$ nejmenší celé číslo ${ displaystyle k}$ tak, že každý graf ${ displaystyle G}$ z ${ displaystyle { mathcal {C}}}$ má ${ displaystyle chi '_ {g} (G) leq k}$ . Jinými slovy, ${ displaystyle chi '_ {g} ({ mathcal {C}})}$ je přesná horní hranice pro herní chromatický index grafů v této třídě. Tato hodnota je známá pro několik standardních tříd grafů a pro některé další omezená:

Kola: ${ displaystyle chi '_ {g} (W_ {3}) = 5}$ a ${ displaystyle chi '_ {g} (W_ {n}) = n + 1}$ když ${ displaystyle n geq 4}$ .^[19]
Lesy : ${ displaystyle chi '_ {g} ({ mathcal {F}} _ { Delta}) leq Delta +1}$ když ${ displaystyle Delta neq 4}$ , a ${ displaystyle 5 leq chi '_ {g} ({ mathcal {F}} _ {4}) leq 6}$ .^[22]
Navíc, pokud každý strom v lese ${ displaystyle F}$ z ${ displaystyle { mathcal {F}} _ {4}}$ se získává rozdělením z a housenka nebo potom neobsahuje žádné dva sousední vrcholy se stupněm 4 ${ displaystyle chi '_ {g} (F) leq 5}$ .^[23]

Otevřené problémy

Horní hranice. Existuje konstanta ${ displaystyle c geq 2}$ takhle ${ displaystyle chi '_ {g} (G) leq Delta (G) + c}$ pro každý graf ${ displaystyle G}$ ? Pokud je to pravda, je ${ displaystyle c = 2}$ dost ?^[19]

Domněnky na velkých minimálních stupních. Existují ${ displaystyle epsilon> 0}$ a celé číslo ${ displaystyle d_ {0}}$ takový, že jakýkoli graf ${ displaystyle G}$ s ${ displaystyle delta (G) geq d_ {0}}$ splňuje ${ displaystyle chi '_ {g} (G) geq (1+ epsilon) delta (G)}$ . ^[20]

Incident zbarvení hra

The výskyt zbarvení hra je hra na barvení grafů, kterou představil Andres,^[24] a podobně jako hra o obarvení vrcholů, kromě Alice a Boba, které vytvářejí vlastní výskyt zbarvení místo správného zbarvení vrcholů. Jeho pravidla jsou následující:

Alice a Bob zbarvují výskyty grafu G se sadou k barev.
Alice a Bob se střídají a správně vybarvují nebarvený výskyt (ve standardní verzi začíná Alice).
Pokud výskyt i není možné správně vybarvit (pro jakoukoli barvu i sousedí s incidentem barevným), pak vyhrává Bob.
Pokud jsou všechny výskyty správně vybarveny, vyhrává Alice.

The chromatické číslo dopadající hry grafu ${ displaystyle G}$ , označeno ${ displaystyle i_ {g} (G)}$ , je minimální počet barev potřebných k tomu, aby Alice tuto hru vyhrála ${ displaystyle G}$ .

Pro každý graf ${ displaystyle G}$ s maximálním stupněm ${ displaystyle Delta}$ , my máme ${ displaystyle { frac {3 Delta -1} {2}}$ .^[24]

Vztahy s jinými pojmy

(inzerát)-Rozklad. Toto je nejlepší horní mez, kterou známe pro obecný případ. Pokud jsou okraje grafu ${ displaystyle G}$ lze rozdělit na dvě sady, z nichž jedna vyvolává graf s arboricita ${ displaystyle a}$ , druhý vyvolává graf s maximálním stupněm ${ displaystyle d}$ , pak ${ displaystyle i_ {g} (G) leq vlevo lfloor { frac {3 Delta (G) -a} {2}} vpravo rfloor + 8a + 3d-1}$ .^[25]
Pokud navíc ${ displaystyle Delta (G) geq 5a + 6d}$ , pak ${ displaystyle i_ {g} (G) leq vlevo lfloor { frac {3 Delta (G) -a} {2}} vpravo rfloor + 8a + d-1}$ .^[25]
Degenerace. Li ${ displaystyle G}$ je k-degenerovaný graf s maximem stupeň ${ displaystyle Delta (G)}$ , pak ${ displaystyle i_ {g} (G) leq 2 Delta (G) + 4k-2}$ . Navíc, ${ displaystyle i_ {g} (G) leq 2 Delta (G) + 3k-1}$ když ${ displaystyle Delta (G) geq 5k-1}$ a ${ displaystyle i_ {g} (G) leq Delta (G) + 8k-2}$ když ${ displaystyle Delta (G) leq 5k-1}$ .^[24]

Třídy grafů

Pro třídu ${ displaystyle { mathcal {C}}}$ grafů označujeme ${ displaystyle i_ {g} ({ mathcal {C}})}$ nejmenší celé číslo ${ displaystyle k}$ tak, že každý graf ${ displaystyle G}$ z ${ displaystyle { mathcal {C}}}$ má ${ displaystyle i_ {g} (G) leq k}$ .

Cesty : Pro ${ displaystyle k geq 13}$ , ${ displaystyle i_ {g} (P_ {k}) = 5}$ .
Cykly : Pro ${ displaystyle k geq 3}$ , ${ displaystyle i_ {g} (C_ {k}) = 5}$ .^[26]
Hvězdy : Pro ${ displaystyle k geq 1}$ , ${ displaystyle i_ {g} (S_ {2k}) = 3k}$ .^[24]
Kola : Pro ${ displaystyle k geq 6}$ , ${ displaystyle i_ {g} (W_ {2k + 1}) = 3k + 2}$ . Pro ${ displaystyle k geq 7}$ , ${ displaystyle i_ {g} (W_ {2k}) = 3k}$ .^[24]
Podgrafy Kola : Pro ${ displaystyle k geq 13}$ , pokud ${ displaystyle G}$ je podgrafem ${ displaystyle W_ {k}}$ mít ${ displaystyle S_ {k}}$ jako podgraf ${ displaystyle i_ {g} (G) = left lceil { frac {3k} {2}} right rceil}$ .^[27]

Otevřené problémy

Je horní mez ${ displaystyle i_ {g} (G) <3 Delta (G) -1}$ těsný pro každou hodnotu ${ displaystyle Delta (G)}$ ?^[24]
Je chromatické číslo incidenční hry monotónním parametrem (tj. Je pro graf alespoň stejně velké) G jako pro jakýkoli podgraf z G) ?^[24]

Poznámky

^ Gardner (1981)
^ Bodlaender (1991)
^ S méně barvami, než je chromatický počet, není správné zbarvení G a tak Alice nemůže vyhrát. S více barvami, než je maximální stupeň, je vždy k dispozici barva pro vybarvení vrcholu, takže Alice nemůže ztratit.
^ Dinski & Zhu (1999)
^ Junosza-Szaniawski & Rożej (2010)
^ Faigle a kol. (1993) a předpokládá Junosza-Szaniawski & Rożej (2010)
^ ^A ^b Dunn a kol. (2014)
^ Sidorowicz (2007) a předpokládá Junosza-Szaniawski & Rożej (2010)
^ Guan & Zhu (1999)
^ Horní hranice Zhu (2008), čímž se zlepšila předchozí hranice 33 palců Kierstead & Trotter (1994), 30 předpokládá Dinski & Zhu (1999), 19 palců Zhu (1999) a 18 palců Kierstead (2000). Dolní mezní hodnota Kierstead & Trotter (1994). Podívejte se na průzkum věnovaný barevnému počtu planárních grafů ve hře Bartnicki a kol. (2007).
^ Sekigushi (2014)
^ On a kol. (2002)
^ Raspaud & Wu (2009)
^ Zhu (2000)
^ Faigle a kol. (1993)
^ ^A ^b ^C ^d Peterin (2007)
^ ^A ^b ^C Sia (2009)
^ ^A ^b Zhu (1999)
^ ^A ^b ^C ^d Lam, Shiu a Xu (1999)
^ ^A ^b ^C Beveridge a kol. (2008)
^ Bartnicki & Grytczuk (2008), zlepšení výsledků na k-degenerovat grafy v Cai & Zhu (2001)
^ Horní mez Δ + 2 o Lam, Shiu a Xu (1999), poté vázáno na Δ + 1 pomocí Erdös a kol. (2004) pro případy Δ = 3 a Δ≥6 a do Andres (2006) pro případ Δ = 5.
^ Podmínky pro lesy s Δ = 4 jsou v Chan & Nong (2014)
^ ^A ^b ^C ^d ^E ^F ^G Andres (2009a), viz také erratum v Andres (2009b)
^ ^A ^b Charpentier & Sopena (2014), rozšiřující výsledky Charpentier & Sopena (2013).
^ Kim (2011), zlepšení podobného výsledku pro k ≥ 7 v Andres (2009a) (viz také erratum v Andres (2009b) )
^ Kim (2011)

Odkazy (chronologické pořadí)

Gardner, Martin (1981). "Matematické hry". Scientific American. Sv. 23.CS1 maint: ref = harv (odkaz)
Bodlaender, Hans L. (1991). "O složitosti některých barevných her". Graf-teoretické koncepty v informatice. Přednášky z informatiky. 484. 30–40. CiteSeerX 10.1.1.18.9992. doi:10.1007/3-540-53832-1_29. ISBN 978-3-540-53832-5.CS1 maint: ref = harv (odkaz)
Faigle, Ulrich; Kern, Walter; Kierstead, Henry A .; Trotter, William T. (1993). „Ve hře Chromatický počet některých tříd grafů“ (PDF). Ars Combinatoria. 35 (17): 143–150.
Kierstead, Henry A .; Trotter, William T. (1994). „Zbarvení planárního grafu s nespolupracujícím partnerem“ (PDF). Journal of Graph Theory. 18 (6): 564–584. doi:10,1002 / jgt.3190180605.CS1 maint: ref = harv (odkaz)
Dinski, Thomas; Zhu, Xuding (1999). Msgstr "Omezeno na chromatický počet grafů hry". Diskrétní matematika. 196 (1–3): 109–115. doi:10.1016 / s0012-365x (98) 00197-6.CS1 maint: ref = harv (odkaz)
Guan, D. J .; Zhu, Xuding (1999). Msgstr "Chromatický počet vnějších rovinných grafů". 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.CS1 maint: ref = harv (odkaz)
Lam, Peter C. B .; Shiu, Wai C .; Xu, Baogang (1999). „Okrajová hra zbarvení grafů“ (PDF). Poznámky k teorii grafů N.Y.. 37: 17–19.CS1 maint: ref = harv (odkaz)
Zhu, Xuding (1999). "Hra zbarvení Počet planárních grafů". Journal of Combinatorial Theory, Series B. 75 (2): 245–258. doi:10.1006 / jctb.1998.1878.CS1 maint: ref = harv (odkaz)
Kierstead, Henry A. (2000). "Jednoduchý konkurenční algoritmus zbarvení grafu". Journal of Combinatorial Theory, Series B. 78 (1): 57–68. doi:10.1006 / jctb.1999.1927.CS1 maint: ref = harv (odkaz)
Zhu, Xuding (2000). "Počet zbarvení hry pseudo dílčí k-stromy “. Diskrétní matematika. 215 (1–3): 245–262. doi:10.1016 / s0012-365x (99) 00237-x.CS1 maint: ref = harv (odkaz)
Cai, Leizhen; Zhu, Xuding (2001). "Chromatický index hry z k-Degenerovat grafy ". Journal of Graph Theory. 36 (3): 144–155. doi:10.1002 / 1097-0118 (200103) 36: 3 <144 :: aid-jgt1002> 3.0.co; 2-f.CS1 maint: ref = harv (odkaz)
On, Wenjie; Hou, Xiaoling; Lih, Ko-Wei; Shao, Jiating; Wang, Weifan; Zhu, Xuding (2002). Msgstr "Okrajové oddíly planárních grafů a jejich čísla barev hry". Journal of Graph Theory. 41 (4): 307–311. doi:10,1002 / jgt.10069.
Erdös, Peter L .; Faigle, Ulrich; Hochstättler, Winfried; Kern, Walter (2004). „Poznámka k barevnému indexu hry“. Teoretická informatika. 313 (3): 371–376. doi:10.1016 / j.tcs.2002.10.002.
Andres, Stephan D. (2006). „Herní chromatický index lesů maximálního stupně Δ ⩾ 5“. Diskrétní aplikovaná matematika. 154 (9): 1317–1323. doi:10.1016 / j.dam.2005.05.031.CS1 maint: ref = harv (odkaz)
Bartnicki, Tomasz; Grytczuk, Jaroslaw; Kierstead, H. A .; Zhu, Xuding (2007). „The Map-Coloring Game“ (PDF). Americký matematický měsíčník. 114 (9): 793–803. doi:10.1080/00029890.2007.11920471. JSTOR 27642332. S2CID 15901267.
Peterin, Iztok (2007). Msgstr "Chromatický počet grafů karteziánských produktů". Elektronické poznámky v diskrétní matematice. 29: 353–357. CiteSeerX 10.1.1.107.111. doi:10.1016 / j.endm.2007.07.060.CS1 maint: ref = harv (odkaz)
Sidorowicz, Elżbieta (2007). „Chromatické číslo hry a počet zbarvení hry kaktusů“. Dopisy o zpracování informací. 102 (4): 147–151. doi:10.1016 / j.ipl.2006.12.003.CS1 maint: ref = harv (odkaz)
Bartnicki, Tomasz; Grytczuk, Jarosław (2008). Msgstr "Poznámka ke hře Chromatický rejstřík grafů". Grafy a kombinatorika. 24 (2): 67–70. doi:10.1007 / s00373-008-0774-z. S2CID 19373685.CS1 maint: ref = harv (odkaz)
Beveridge, Andrew; Bohman, Tom; Friezeb, Alan; Pikhurko, Oleg (2008). "Herní chromatický index grafů s daným omezením stupňů". Teoretická informatika. 407 (1–3): 242–249. doi:10.1016 / j.tcs.2008.05.026.CS1 maint: ref = harv (odkaz)
Zhu, Xuding (2008). Msgstr "Vylepšená aktivační strategie pro značkovací hru". Journal of Combinatorial Theory, Series B. 98 (1): 1–18. doi:10.1016 / j.jctb.2007.04.004.CS1 maint: ref = harv (odkaz)
Andres, Stefan D. (2009). "Chromatické číslo hry Incident". Diskrétní aplikovaná matematika. 157 (9): 1980–1987. doi:10.1016 / j.dam.2007.10.021.
Andres, Stefan D. (2009). „Erratum to: The impact game chromatic number“. Diskrétní aplikovaná matematika. 158 (6): 728. doi:10.1016 / j.dam.2009.11.017.
Raspaud, André; Wu, Jiaojiao (2009). Msgstr "Chromatický počet toroidních sítí". Dopisy o zpracování informací. 109 (21–22): 1183–1186. doi:10.1016 / j.ipl.2009.08.001.CS1 maint: ref = harv (odkaz)
Sia, Charmaine (2009). „Hra Chromatický počet některých rodin grafů kartézských produktů“ (PDF). AKCE International Journal of Graphs and Combinatorics. 6 (2): 315–327. Archivovány od originál (PDF) dne 14.11.2011. Citováno 2014-07-16.CS1 maint: ref = harv (odkaz)
Junosza-Szaniawski, Konstanty; Rożej, Łukasz (2010). „Herní chromatický počet grafů s místně ohraničeným počtem cyklů“. Dopisy o zpracování informací. 110 (17): 757–760. doi:10.1016 / j.ipl.2010.06.004.CS1 maint: ref = harv (odkaz)
Kim, John Y. (2011). Msgstr "Chromatický počet cest a podgrafů kol ve hře". Diskrétní aplikovaná matematika. 159 (8): 683–694. doi:10.1016 / j.dam.2010.01.001.CS1 maint: ref = harv (odkaz)
Charpentier, Clément; Sopena, Éric (2013). Incidentní barevná hra a arboricita grafů. Přednášky z informatiky. 8288. 106–114. arXiv:1304.0166. doi:10.1007/978-3-642-45278-9_10. ISBN 978-3-642-45277-2. S2CID 14707501.CS1 maint: ref = harv (odkaz)
Chan, Wai H .; Nong, Ge (2014). „Herní chromatický index některých stromů maximálního stupně 4“. Diskrétní aplikovaná matematika. 170: 1–6. doi:10.1016 / j.dam.2014.01.003.CS1 maint: ref = harv (odkaz)
Sekigushi, Yosuke (2014). „Hra zbarvuje počet rovinných grafů s daným obvodem“. Diskrétní matematika. 300: 11–16. doi:10.1016 / j.disc.2014.04.011.CS1 maint: ref = harv (odkaz)
Charpentier, Clément; Sopena, Éric (2014). "Chromatický počet výskytů hry (inzerát)-rozložitelné grafy ". Journal of Discrete Algorithms. 31: 14–25. doi:10.1016 / j.jda.2014.10.001.CS1 maint: ref = harv (odkaz)
Dunn, Charles; Larsen, Victor; Lindke, Kira; Retter, Troy; Toci, Dustin (2014). "Hra chromatický počet stromů a lesů". arXiv:1410.5223 [math.CO ].

[1] Gardner (1981)

[2] Bodlaender (1991)

[3] S méně barvami, než je chromatický počet, není správné zbarvení G a tak Alice nemůže vyhrát. S více barvami, než je maximální stupeň, je vždy k dispozici barva pro vybarvení vrcholu, takže Alice nemůže ztratit.

[4] Dinski & Zhu (1999)

[5] Junosza-Szaniawski & Rożej (2010)

[6] Faigle a kol. (1993) a předpokládá Junosza-Szaniawski & Rożej (2010)

[dunn2014-7] A ^b Dunn a kol. (2014)

[8] Sidorowicz (2007) a předpokládá Junosza-Szaniawski & Rożej (2010)

[9] Guan & Zhu (1999)

[10] Horní hranice Zhu (2008), čímž se zlepšila předchozí hranice 33 palců Kierstead & Trotter (1994), 30 předpokládá Dinski & Zhu (1999), 19 palců Zhu (1999) a 18 palců Kierstead (2000). Dolní mezní hodnota Kierstead & Trotter (1994). Podívejte se na průzkum věnovaný barevnému počtu planárních grafů ve hře Bartnicki a kol. (2007).

[11] Sekigushi (2014)

[12] On a kol. (2002)

[13] Raspaud & Wu (2009)

[14] Zhu (2000)

[15] Faigle a kol. (1993)

[peterin2007-16] A ^b ^C ^d Peterin (2007)

[sia2009-17] A ^b ^C Sia (2009)

[zhu1999-18] A ^b Zhu (1999)

[lsz1999-19] A ^b ^C ^d Lam, Shiu a Xu (1999)

[bevetal2008-20] A ^b ^C Beveridge a kol. (2008)

[21] Bartnicki & Grytczuk (2008), zlepšení výsledků na k-degenerovat grafy v Cai & Zhu (2001)

[22] Horní mez Δ + 2 o Lam, Shiu a Xu (1999), poté vázáno na Δ + 1 pomocí Erdös a kol. (2004) pro případy Δ = 3 a Δ≥6 a do Andres (2006) pro případ Δ = 5.

[23] Podmínky pro lesy s Δ = 4 jsou v Chan & Nong (2014)

[Andres2009-24] A ^b ^C ^d ^E ^F ^G Andres (2009a), viz také erratum v Andres (2009b)

[charpSop2014-25] A ^b Charpentier & Sopena (2014), rozšiřující výsledky Charpentier & Sopena (2013).

[26] Kim (2011), zlepšení podobného výsledku pro k ≥ 7 v Andres (2009a) (viz také erratum v Andres (2009b) )

[27] Kim (2011)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]