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 , označeno , je minimální počet barev potřebných k tomu, aby Alice vyhrála vrcholnou hru s barvami . Triviálně, pro každý graf , my máme , kde je chromatické číslo z a jeho maximum stupeň.[3]
Vztah k jiným pojmům
Acyklické zbarvení. Každý graf s acyklické chromatické číslo má .[4]
Značkovací hra. Pro každý graf , , kde je hra zbarvení číslo z . 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 patří nanejvýš cykly, pak .[5]
Třídy grafů
Pro třídu grafů označujeme nejmenší celé číslo tak, že každý graf z má . Jinými slovy, 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: .[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: .[8]
- Vnější rovinné grafy: .[9]
- Rovinné grafy: .[10]
- Rovinné grafy daného obvod: ,[11] , , .[12]
- Toroidní mřížky: .[13]
- Částečný k-stromy: .[14]
- Intervalové grafy: , kde je pro graf o velikosti největší klika.[15]
Kartézské výrobky.Chromatické číslo hry kartézského produktu není omezen funkcí a . Zejména herní chromatické číslo jakéhokoli úplného bipartitního grafu se rovná 3, ale neexistuje žádná horní mez pro pro libovolné .[16]
- Pro jednu hranu máme:[16]
- Stromy:
- Kola: -li [17]
- Kompletní bipartitní grafy: -li [17]
Otevřené problémy
Tyto otázky jsou k tomuto datu stále otevřené.
- 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.
- 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 ?
- Dohad: Je je les, existuje takhle a .
- Nechat být třída grafů taková, že pro všechny , tady existuje takhle a . V čem jsou rodiny grafů ?
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 , označeno , je minimální počet barev potřebných k tomu, aby Alice tuto hru vyhrála .
Obecný případ
Pro každý graf G, . 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 pro libovolné velké hodnoty .[20]
Dohad. Tady je takový, že pro libovolný graf , my máme .
Tato domněnka je pravdivá, když je dostatečně velký ve srovnání s počtem vrcholů v .[20]
- Arboricita. Nechat být arboricita grafu . Každý graf s maximem stupeň má .[21]
Třídy grafů
Pro třídu grafů označujeme nejmenší celé číslo tak, že každý graf z má . Jinými slovy, 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: a když .[19]
- Lesy : když , a .[22]
Navíc, pokud každý strom v lese z se získává rozdělením z a housenka nebo potom neobsahuje žádné dva sousední vrcholy se stupněm 4 .[23]
Otevřené problémy
Horní hranice. Existuje konstanta takhle pro každý graf ? Pokud je to pravda, je dost ?[19]
Domněnky na velkých minimálních stupních. Existují a celé číslo takový, že jakýkoli graf s splňuje . [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 , označeno , je minimální počet barev potřebných k tomu, aby Alice tuto hru vyhrála .
Pro každý graf s maximálním stupněm , my máme .[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 lze rozdělit na dvě sady, z nichž jedna vyvolává graf s arboricita , druhý vyvolává graf s maximálním stupněm , pak .[25]
Pokud navíc , pak .[25] - Degenerace. Li je k-degenerovaný graf s maximem stupeň , pak . Navíc, když a když .[24]
Třídy grafů
Pro třídu grafů označujeme nejmenší celé číslo tak, že každý graf z má .
- Cesty : Pro , .
- Cykly : Pro , .[26]
- Hvězdy : Pro , .[24]
- Kola : Pro , . Pro , .[24]
- Podgrafy Kola : Pro , pokud je podgrafem mít jako podgraf .[27]
Otevřené problémy
- Je horní mez těsný pro každou hodnotu ?[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 ].