グラフ塗り絵ゲーム

与えられたグラフ上のアリスとボブによる頂点彩色ゲーム。ここで、「A」とラベル付けされた頂点はアリスが彩色し、「B」とラベル付けされた頂点はボブが彩色する。プレイヤーは（アリスから始めて）交代でグラフ上の頂点を適切に彩色する。最終的にグラフ全体が適切に彩色されればアリスの勝ち。いずれかの時点で適切に彩色できなくなった頂点があればボブの勝ち。

ゲームの彩色数 は、アリスがグラフ上の頂点彩色ゲームに勝つために必要な最小の色数である。このグラフでは、は直積^[1]であるため、 となる。${\displaystyle \chi _{g}(G)}$ ${\displaystyle G}$ ${\displaystyle \chi _{g}(G)=3}$ ${\displaystyle S_{5}\square P_{2}}$

数学における未解決問題

アリスがk色のグラフG上の頂点彩色ゲームで勝利戦略を持っているとします。k +1色に対しても同じ戦略を持っていますか？

数学におけるさらなる未解決問題

グラフ彩色ゲームは、グラフ理論に関連する数学ゲームです。彩色ゲーム問題は、よく知られたグラフ彩色問題のゲーム理論版として生まれました。彩色ゲームでは、2人のプレイヤーが与えられた色のセットを用いて、ゲームに応じた特定のルールに従ってグラフの彩色を行います。一方のプレイヤーはグラフの彩色を完成させようとし、もう一方のプレイヤーはそれを阻止しようとします。

頂点カラーリングゲーム

頂点彩色ゲームは1981年にスティーブン・ブラムスによって地図彩色ゲームとして導入され^{[2] [3]}、10年後にボドランダーによって再発見されました。^[4]そのルールは以下のとおりです。

1. アリスとボブはグラフGの頂点をk色のセットで色付けします。
2. アリスとボブは交代で、色付けされていない頂点を適切に色付けします(標準バージョンでは、アリスが開始します)。
3. 頂点vを適切に色付けできない場合 (どの色でも、v の隣接頂点がその色で色付けされている場合)、Bob が勝ちます。
4. グラフが完全に色付けされていれば、アリスが勝ちます。

グラフ のゲーム彩色数は と表記され、アリスが 上の頂点彩色ゲームに勝つために必要な最小の色数です。当然のことながら、任意のグラフ に対して が成り立ちます。ここで はの彩色数であり、最大次数は です。^[5]${\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)}$

1991年のボドランダーの論文^[6]では、計算複雑性は「興味深い未解決問題」として残されていました。このゲームがPSPACE完全であることが証明されたのは2020年になってからでした。^[7]

他の概念との関係

非巡回彩色。非巡回彩色数を持つグラフはすべて を持つ。^[8]${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle \chi _{g}(G)\leq k(k+1)}$

マーキングゲーム。任意のグラフ,について、 は のゲーム彩色数です。グラフのゲーム彩色数のほぼすべての既知の上限は、ゲーム彩色数の境界から得られます。 ${\displaystyle G}$ ${\displaystyle \chi _{g}(G)\leq col_{g}(G)}$ ${\displaystyle col_{g}(G)}$ ${\displaystyle G}$

辺のサイクル制約。グラフの各辺が最大でもサイクルに属する場合、 となる。^[9]${\displaystyle G}$ ${\displaystyle c}$ ${\displaystyle \chi _{g}(G)\leq 4+c}$

グラフクラス

グラフのクラスに対して、のすべてのグラフが となるような最小の整数を で表します。言い換えれば、はこのクラスのグラフのゲーム彩色数の正確な上限です。この値はいくつかの標準的なグラフクラスで知られており、他のいくつかのクラスでは有界です。 ${\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}})}$

• 森林: [ ^10] 3次の頂点を持たない森林のゲーム彩色数を決定するための簡単な基準が知られている。^[11]最大次数が3の森林であっても、3次の頂点を持つ森林のゲーム彩色数を決定するのは難しいと思われる。${\displaystyle \chi _{g}({\mathcal {F}})=4}$
• サボテン：[ ^12]${\displaystyle \chi _{g}({\mathcal {C}})=5}$
• 外平面グラフ: [ ^13]${\displaystyle 6\leq \chi _{g}({\mathcal {O}})\leq 7}$
• 平面グラフ：[ ^14]${\displaystyle 7\leq \chi _{g}({\mathcal {P}})\leq 17}$
• 与えられた内周の平面グラフ：、^[15]、、、[ ^16]${\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}$
• トロイダルグリッド： [ ^17]${\displaystyle \chi _{g}({{\mathcal {T}}G})=5}$
• 部分k木: [ ^18]${\displaystyle \chi _{g}({\mathcal {T}}_{k})\leq 3k+2}$
• 区間グラフ：、グラフの最大クリークの大きさ。^[19]${\displaystyle 2\omega \leq \chi _{g}({\mathcal {I}})\leq 3\omega -2}$ ${\displaystyle \omega }$

直積。直積 のゲーム彩色数はおよびの関数で有界ではない。特に、任意の完全二部グラフのゲーム彩色数は3 に等しいが、任意の に対しての上限は存在しない。^[20]一方、 のゲーム彩色数はおよび の関数で上方に有界である。特に、と が両方とも 最大で である場合、 となる。^[21]${\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}}$

• 単一のエッジの場合、次の式が得られます。^[20]

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

• 星については次のようになります: ^[1]

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

• 木々 :${\displaystyle \chi _{g}(T_{1}\square T_{2})\leq 12.}$
• ホイール：if ^[1]${\displaystyle \chi _{g}(P_{2}\square W_{n})=5}$ ${\displaystyle n\geq 9.}$
• 完全二部グラフの場合：^[1]${\displaystyle \chi _{g}(P_{2}\square K_{m,n})=5}$ ${\displaystyle m,n\geq 5.}$

未解決の問題

これらの疑問は今日まで未解決のままです。

アリスのためのより多くの色

• アリスがk色のグラフG上の頂点彩色ゲームで勝利戦略を持っていると仮定します。彼女はk+1色に対しても勝利戦略を持っているでしょうか？色数が多い方がアリスにとって有利に見えるため、答えは「はい」と予想されます。しかし、この命題が真であるという証明は存在しません。^[22]
  
• グラフG上のk色の頂点彩色ゲームでアリスが勝利する戦略を持っている場合、 f(k)を持つG上の勝利戦略を持つような関数fは存在しますか ?前の質問の緩和版です。
  

他の概念との関係

• 単調なグラフのクラス（すなわち、部分グラフによって閉じられたグラフのクラス）がゲーム彩色数を有界とすると仮定する。このグラフのクラスはゲーム彩色数を有界とすることは真か ？ ^[22]
• 単調なグラフのクラス（つまり、部分グラフによって閉じられたグラフのクラス）のゲーム彩色数が有界であるとします。このグラフのクラスは樹状性が有界であるというのは本当でしょうか ？
• 有界ゲーム彩色数のグラフの単調クラスには有界非巡回彩色数があるというのは本当ですか ?

最大度数を下げる

• 予想:が森林である場合、かつ となるような が存在する。^[11]${\displaystyle F}$ ${\displaystyle F'\subseteq F}$ ${\displaystyle \Delta (F')\leq \chi _{g}(F)}$ ${\displaystyle \chi _{g}(F')=\chi _{g}(F)}$
• をグラフのクラスとし、任意の に対して、かつ が存在するものとします。にはどのようなグラフの族が含まれますか ？${\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}}}$

ハイパーキューブ

• 任意の超立方体に対して は真でしょうか ？に対しては真であることが知られています。^[20]${\displaystyle \chi _{g}(G)=n+1}$ ${\displaystyle Q_{n}}$
  ${\displaystyle n\leq 4}$

エッジカラーリングゲーム

ラム、シウ、ズー^[23]によって提唱された辺彩色ゲームは、頂点彩色ゲームに似ていますが、アリスとボブが真頂点彩色ではなく真辺彩色を構築する点が異なります。そのルールは以下のとおりです。

1. アリスとボブはグラフGのエッジをk色のセットで色付けしています。
2. アリスとボブは交代で、色付けされていないエッジを適切に色付けしています(標準バージョンでは、アリスが開始します)。
3. エッジeを適切に色付けできない場合 (どの色でも、eはそれと同じ色で色付けされたエッジに隣接している)、Bob が勝ちます。
4. グラフのエッジが完全に色付けされている場合、アリスが勝ちます。

このゲームは、折れ線グラフ上の頂点彩色ゲームの特殊なケースと見なすことができますが、科学文献では主に別のゲームとして扱われています。グラフ のゲーム彩色指数は と表記され、アリスが 上でこのゲームに勝つために必要な最小の色数です。 ${\displaystyle G}$ ${\displaystyle \chi '_{g}(G)}$ ${\displaystyle G}$

一般的なケース

あらゆるグラフGに対して、これらの境界に達するグラフが存在するが、この上限に達する既知のグラフはすべて最大次数が小さい。^[23]の任意の大きな値 に対して、 となるグラフが存在する。^[24]${\displaystyle \chi '(G)\leq \chi '_{g}(G)\leq 2\Delta (G)-1}$ ${\displaystyle \chi '_{g}(G)>1.008\Delta (G)}$ ${\displaystyle \Delta (G)}$

予想。 任意のグラフ に対して となるような が存在する。${\displaystyle \epsilon >0}$ ${\displaystyle G}$ ${\displaystyle \chi '_{g}(G)\leq (2-\epsilon )\Delta (G)}$
この予想はが の頂点数に比べて十分に大きいときに成り立つ。^[24]${\displaystyle \Delta (G)}$ ${\displaystyle G}$

• 樹木性。グラフ の樹木性をとする。最大次数を持つすべてのグラフはを持つ。^[25]${\displaystyle a(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \Delta (G)}$ ${\displaystyle \chi '_{g}(G)\leq \Delta (G)+3a(G)-1}$

グラフクラス

グラフのクラスに対して、のすべてのグラフが となるような最小の整数を で表します。言い換えれば、はこのクラスのグラフのゲーム彩色指数の正確な上限です。この値はいくつかの標準的なグラフクラスで知られており、他のいくつかのクラスでは有界です。 ${\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}})}$

• 車輪：そしていつ。^[23]${\displaystyle \chi '_{g}(W_{3})=5}$ ${\displaystyle \chi '_{g}(W_{n})=n+1}$ ${\displaystyle n\geq 4}$
• 森林 ：、のとき。^[26]さらに、の森林のすべての木がキャタピラー木から細分化して得られるか、または2つの隣接する次数4の頂点を含まない場合、。^[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}$

未解決の問題

上限。各グラフに対して となる定数は存在するか ？もしそれが真なら、 で十分か？^[23]${\displaystyle c\geq 2}$ ${\displaystyle \chi '_{g}(G)\leq \Delta (G)+c}$ ${\displaystyle G}$ ${\displaystyle c=2}$

大きな最小次数に関する予想。 任意のグラフがを満たすような整数aとaが存在する。${\displaystyle \epsilon >0}$ ${\displaystyle d_{0}}$ ${\displaystyle G}$ ${\displaystyle \delta (G)\geq d_{0}}$ ${\displaystyle \chi '_{g}(G)\geq (1+\epsilon )\delta (G)}$ ^[24]

発生率塗り絵ゲーム

発生彩色ゲームは、Andres ^[28]によって導入されたグラフ彩色ゲームであり、頂点彩色ゲームに似ていますが、アリスとボブが適切な頂点彩色ではなく適切な発生彩色を構成する点が異なります。そのルールは以下のとおりです。

1. アリスとボブはグラフGの発生をk色のセットで色付けしています。
2. アリスとボブは交代で、色付けされていない出来事を適切に色付けしています (標準バージョンでは、アリスが始めます)。
3. 発生事象 iを適切に色付けできない場合(どの色でも、 iは同じ色で色付けされた発生事象に隣接している場合)、Bob が勝ちます。
4. すべての出来事が適切に色付けされていれば、アリスが勝ちます。

グラフ の発生ゲーム彩色数は と表され、上でアリスがこのゲームに勝つために必要な最小の色数です。 ${\displaystyle G}$ ${\displaystyle i_{g}(G)}$ ${\displaystyle G}$

最大次数を持つすべてのグラフに対して、 が成り立つ。^[28]${\displaystyle G}$ ${\displaystyle \Delta }$ ${\displaystyle {\frac {3\Delta -1}{2}}<i_{g}(G)<3\Delta -1}$

他の概念との関係

• (a,d)分解。これは一般的なケースにおける我々が知る最良の上限である。グラフの辺を2つの集合に分割でき、そのうちの1つが樹状度、もう1つが最大次数 のグラフを誘導する場合、 と。^[29]さらに の場合、 となる。^[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}$
• 退化。が最大次数のk退化したグラフである場合、 となる。さらに、のとき、 のときとなる。^[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}$

グラフクラス

グラフのクラスについて、のすべてのグラフが を持つような最小の整数を で表します。 ${\displaystyle {\mathcal {C}}}$ ${\displaystyle i_{g}({\mathcal {C}})}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle i_{g}(G)\leq k}$

• パス : 、の場合。${\displaystyle k\geq 13}$ ${\displaystyle i_{g}(P_{k})=5}$
• サイクル ：の場合、。^[30]${\displaystyle k\geq 3}$ ${\displaystyle i_{g}(C_{k})=5}$
• 星 ：、。^[28]${\displaystyle k\geq 1}$ ${\displaystyle i_{g}(S_{2k})=3k}$
• ホイール ： 、、。[ 28 ^]${\displaystyle k\geq 6}$ ${\displaystyle i_{g}(W_{2k+1})=3k+2}$ ${\displaystyle k\geq 7}$ ${\displaystyle i_{g}(W_{2k})=3k}$
• 車輪のサブグラフ ： について、 が のサブグラフであり がサブグラフである場合、となる。^[31]${\displaystyle k\geq 13}$ ${\displaystyle G}$ ${\displaystyle W_{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle i_{g}(G)=\left\lceil {\frac {3k}{2}}\right\rceil }$

未解決の問題

• のあらゆる値に対して上限は厳密ですか ？^[28]${\displaystyle i_{g}(G)<3\Delta (G)-1}$ ${\displaystyle \Delta (G)}$
• 発生ゲームの彩色数は単調なパラメータか（つまり、グラフGの場合とGの任意のサブグラフの場合で少なくとも同じくらい大きいか）？^[28]

注記

1. シーア (2009)
2. ガードナー（1981）
3. Bartnicki et al. (2007)
4. ボドランダー（1991）
5. 彩色数より少ない色数では、 Gを適切に彩色することは不可能であり、アリスは勝つことができません。最大次数より多い色数では、頂点を彩色するための色が常に存在するため、アリスは負けることはありません。
6. ボドランダー（1991）
7. コスタ、ペソア、ソアレス、サンパイオ (2020)
8. ディンスキーとジュー (1999)
9. ユノシャ=シャニャフスキ & ロジェイ (2010)
10. Faigle et al. (1993)、Junosza-Szaniawski & Rożej (2010) によって示唆されている
11. Dunn et al. (2014)
12. Sidorowicz (2007)、および Junosza-Szaniawski & Rożej (2010) が示唆
13. グアン＆ジュー (1999)
14. 上限はZhu (2008)によるもので、Kierstead & Trotter (1994)の33、Dinski & Zhu (1999)の30、Zhu (1999)の19、Kierstead (2000)の18という以前の上限を上回っている。下限はKierstead & Trotter (1994)が主張している。平面グラフのゲーム彩色数に関するサーベイはBartnicki et al. (2007)を参照のこと。
15. 関串 (2014)
16. He et al. (2002)
17. ラスパウド＆ウー（2009）
18. 朱（2000）
19. フェイグルら（1993）
20. ピーターリン (2007)
21. ブラッドショー（2021）
22. 朱アブ (1999)
23. ラム、シウ、シュウ (1999)
24. Beveridge et al. (2008)
25. Bartnicki & Grytczuk (2008)、 Cai & Zhu (2001)のk-退化グラフに関する結果の改善
26. Δ+2の上限はLam、Shiu & Xu (1999)によって示され、Δ+1の上限はΔ=3およびΔ≥6の場合についてはErdösら(2004)によって示され、Δ=5の場合についてはAndres (2006)によって示されました。
27. Δ=4の森林の状況はChan & Nong (2014)に記載されている。
28. Andres (2009a)、Andres (2009b) の正誤表も参照
29. Charpentier & Sopena (2014)、Charpentier & Sopena (2013)の結果を拡張したもの。
30. k ≥ 7の同様の結果を改良（Andres (2009b)の訂正も参照）
31. キム（2011）

参考文献（年代順）

• ガードナー、マーティン (1981). 「数学ゲーム」.サイエンティフィック・アメリカン. 第23巻.
• Bodlaender, Hans L. (1991). 「いくつかの彩色ゲームの複雑さについて」.コンピュータサイエンスにおけるグラフ理論的概念. コンピュータサイエンス講義ノート. 第484巻. pp.  30– 40. CiteSeerX  10.1.1.18.9992 . doi :10.1007/3-540-53832-1_29. ISBN 978-3-540-53832-5。
• フェイグル, ウルリッヒ; カーン, ウォルター; キアーステッド, ヘンリー A.;トロッター, ウィリアム T. (1993). 「グラフのいくつかのクラスのゲーム彩色数について」(PDF) . Ars Combinatoria . 35 (17): 143– 150. 2014年6月6日時点のオリジナルよりアーカイブ(PDF) . 2014年6月6日閲覧.
• Kierstead, Henry A.; Trotter, William T. (1994). 「非協力的なパートナーによる平面グラフ彩色」(PDF) . Journal of Graph Theory . 18 (6): 564– 584. doi :10.1002/jgt.3190180605. 2014年7月14日時点のオリジナルよりアーカイブ(PDF) . 2014年6月10日閲覧.
• Dinski, Thomas; Zhu, Xuding (1999). 「グラフのゲーム彩色数の境界」.離散数学. 196 ( 1–3 ): 109–115 . doi : 10.1016/s0012-365x(98)00197-6 .
• Guan, DJ; Zhu, Xuding (1999). 「外平面グラフのゲーム彩色数」. 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). 「グラフのエッジゲーム彩色」(PDF) . Graph Theory Notes NY . 37 : 17–19 . 2016年3月3日時点のオリジナルよりアーカイブ(PDF) . 2014年7月7日閲覧.
• Zhu, Xuding (1999). 「平面グラフのゲーム彩色数」.組合せ理論ジャーナル, シリーズB. 75 ( 2): 245– 258. doi : 10.1006/jctb.1998.1878 .
• Kierstead, Henry A. (2000). 「単純な競合グラフ彩色アルゴリズム」. Journal of Combinatorial Theory, Series B. 78 ( 1): 57– 68. doi : 10.1006/jctb.1999.1927 .
• Zhu, Xuding (2000). 「擬似部分k木のゲーム彩色数」.離散数学. 215 ( 1–3 ): 245–262 . doi :10.1016/s0012-365x(99)00237-x.
• Cai, Leizhen; Zhu, Xuding (2001). 「 k-縮退グラフのゲーム彩色指数」. Journal of Graph Theory . 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). 「平面グラフの辺分割とゲーム彩色数」. Journal of Graph Theory . 41 (4): 307– 311. doi : 10.1002/jgt.10069 . S2CID  20929383.
• エルデシュ、ピーター L.ファイグル、ウルリッヒ。ホッホシュテットラー、ヴィンフリート。ウォルター・カーン (2004)。 「木のゲームクロマチックインデックスに関するメモ」。理論的なコンピューターサイエンス。313 (3): 371–376。土井: 10.1016/j.tcs.2002.10.002。
• Andres, Stephan D. (2006). 「最大次数 Δ ⩾ 5 の森林のゲーム彩度指数」.離散応用数学. 154 (9): 1317– 1323. doi :10.1016/j.dam.2005.05.031.
• Bartnicki, Tomasz; Grytczuk, Jaroslaw; Kierstead, HA; Zhu, Xuding (2007). 「地図塗り絵ゲーム」(PDF) . American Mathematical Monthly . 114 (9): 793– 803. doi :10.1080/00029890.2007.11920471. JSTOR  27642332. S2CID  15901267. 2014年7月14日時点のオリジナルよりアーカイブ(PDF) . 2014年7月9日閲覧.
• Peterin, Iztok (2007). 「直積グラフのゲーム彩色数」. Electronic Notes in Discrete Mathematics . 29 : 353– 357. CiteSeerX  10.1.1.107.111 . doi :10.1016/j.endm.2007.07.060.
• Sidorowicz, Elżbieta (2007). 「サボテンのゲーム彩色数とゲーム着色数」 .情報処理レター. 102 (4): 147– 151. doi :10.1016/j.ipl.2006.12.003.
• Bartnicki, Tomasz; Grytczuk, Jarosław (2008). 「グラフのゲーム彩色指数に関するノート」.グラフと組合せ論. 24 (2): 67– 70. doi :10.1007/s00373-008-0774-z. S2CID  19373685.
• Beveridge, Andrew; Bohman, Tom; Friezeb, Alan; Pikhurko, Oleg (2008). 「次数に制約のあるグラフのゲーム彩色指数」.理論計算機科学. 407 ( 1–3 ): 242– 249. doi :10.1016/j.tcs.2008.05.026.
• Zhu, Xuding (2008). 「マーキングゲームのための洗練された活性化戦略」.組合せ理論ジャーナル, シリーズB. 98 ( 1): 1– 18. doi : 10.1016/j.jctb.2007.04.004 .
• アンドレス、ステファン・D. (2009). 「インシデンスゲーム彩色数」.離散応用数学. 157 (9): 1980– 1987. doi : 10.1016/j.dam.2007.10.021 .
• Andres, Stefan D. (2009). 「エラータ：インシデンスゲーム彩色数」.離散応用数学. 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
• Raspaud, André; Wu, Jiaojiao (2009). 「トロイダルグリッドのゲーム彩色数」.情報処理レター. 109 ( 21–22 ): 1183–1186 . doi :10.1016/j.ipl.2009.08.001.
• Sia, Charmaine (2009). 「いくつかのカルテシアン積グラフ族のゲーム彩色数」(PDF) . AKCE International Journal of Graphs and Combinatorics . 6 (2): 315– 327. 2011年11月14日時点のオリジナル( PDF)からアーカイブ。 2014年7月16日閲覧。
• Junosza-Szaniawski, Konstanty; Rożej, Łukasz (2010). 「局所的に閉路数が制限されたグラフのゲーム彩色数」情報処理レター. 110 (17): 757– 760. doi :10.1016/j.ipl.2010.06.004.
• Kim, John Y. (2011). 「インシデンスゲームにおけるパスの彩色数と車輪の部分グラフ」.離散応用数学. 159 (8): 683– 694. doi : 10.1016/j.dam.2010.01.001 .
• シャルパンティエ, クレマン; ソペナ, エリック (2013). 「発生彩色ゲームとグラフの樹状性」.組合せアルゴリズム. コンピュータサイエンス講義ノート. 第8288巻. pp.  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). 「最大次数4のいくつかの木のゲーム彩色指数」.離散応用数学. 170 : 1–6 . doi : 10.1016/j.dam.2014.01.003 .
• 関串 洋介 (2014). 「与えられた内周を持つ平面グラフのゲーム彩色数」.離散数学. 300 : 11–16 . doi :10.1016/j.disc.2014.04.011.
• Charpentier, Clément; Sopena, Éric (2014). 「 (a,d)-分解可能グラフのインシデンスゲーム彩色数」. Journal of Discrete Algorithms . 31 : 14– 25. doi :10.1016/j.jda.2014.10.001. S2CID  1102795.
• ダン, チャールズ; ラーセン, ビクター; リンケ, キラ; レッター, トロイ; トチ, ダスティン (2014). 「木と森のゲーム彩色数」. arXiv : 1410.5223 [math.CO].
• Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). 「2つのグラフ彩色ゲームのPSPACE完全性」.理論計算機科学. 824– 825: 36– 45. doi : 10.1016/j.tcs.2020.03.022 . S2CID  218777459.
• ブラッドショー, ピーター (2021). 「制限付き二色部分グラフによるグラフ彩色：II. グラフ彩色ゲーム」. Journal of Graph Theory . 100 (2): 371– 383. arXiv : 2008.13275 . doi :10.1002/jgt.22786. S2CID  221377336.