Jeu de coloration de graphe

Le jeu de coloration de graphes est un jeu mathématique qui se joue sur un graphe. Ce jeu est une version ludique du problème de coloriage de graphes.

Deux joueurs colorient tour à tour un graphe en suivant certaines règles ; le premier joueur tente de colorier le graphe avec succès, tandis que l'autre essaie de l'en empêcher.

Le jeu de coloriage de sommets a été introduit en 1981 par Steven Brams^[1],[2] et redécouvert dix ans plus tard par Bodlaender^[3]. Ses règles sont les suivantes :

1. On choisit un nombre k de couleurs
2. Alice et Bob colorient chacun leur tour un sommet non coloré (dans la version standard, Alice commence).
3. Si un sommet v est impossible à colorier correctement (pour toute couleur, v a un voisin coloré avec cette couleur), alors Bob gagne.
4. Si le graphe est entièrement coloré, alors Alice gagne.

Le nombre chromatique ludique d'un graphe ${\displaystyle G}$, noté ${\displaystyle \chi _{g}(G)}$ est le nombre minimum de couleurs nécessaires à Alice pour posséder une stratégie gagnante. De façon évidente, pour tout graphe ${\displaystyle G}$, on a ${\displaystyle \chi (G)\leq \chi _{g}(G)\leq \Delta (G)+1}$, où ${\displaystyle \chi (G)}$ est le nombre chromatique de ${\displaystyle G}$ et ${\displaystyle \Delta (G)}$ son degré maximal.

En 2020, il a été prouvé que le jeu est PSPACE-complet^[4].

Coloration acyclique

Tout graphe ${\displaystyle G}$ avec nombre chromatique acyclique ${\displaystyle k}$ a ${\displaystyle \chi _{g}(G)\leq k(k+1)}$.

Arêtes avec peu de cycles

Si chaque arête d'un graphe ${\displaystyle G}$ appartient à au plus ${\displaystyle c}$ cycles, puis ${\displaystyle \chi _{g}(G)\leq 4+c}$.

Pour une classe ${\displaystyle {\mathcal {C}}}$ de graphes, on appelle ${\displaystyle \chi _{g}({\mathcal {C}})}$ le plus petit entier ${\displaystyle k}$ tel que chaque graphe ${\displaystyle G}$ de ${\displaystyle {\mathcal {C}}}$ vérifie${\displaystyle \chi _{g}(G)\leq k}$.

• Forêts : ${\displaystyle \chi _{g}({\mathcal {F}})=4}$ Des critères simples sont connus pour déterminer le nombre chromatique de jeu d'une forêt sans sommet de degré 3.
• Cactus : ${\displaystyle \chi _{g}({\mathcal {C}})=5}$.
• Graphes planaires externes : ${\displaystyle 6\leq \chi _{g}({\mathcal {O}})\leq 7}$.
• Graphes planaires : ${\displaystyle 7\leq \chi _{g}({\mathcal {P}})\leq 17}$.
• Graphes planaires de maille donnée : ${\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}$.
• Grilles toroïdales : ${\displaystyle \chi _{g}({{\mathcal {T}}G})=5}$.
• k-arbres : ${\displaystyle \chi _{g}({\mathcal {T}}_{k})\leq 3k+2}$.
• Graphes d'intervalles : ${\displaystyle 2\omega \leq \chi _{g}({\mathcal {I}})\leq 3\omega -2}$, où ${\displaystyle \omega }$ est pour un graphe la taille de sa plus grande clique.

Produits cartésiens

Le nombre chromatique ludique du produit cartésien ${\displaystyle G\square H}$ n'est pas borné par une fonction de ${\displaystyle \chi _{g}(G)}$ et ${\displaystyle \chi _{g}(H)}$. En particulier, le nombre chromatique ludique de tout graphe biparti complet ${\displaystyle K_{n,n}}$ est égal à 3, mais il n'y a pas de limite supérieure pour ${\displaystyle \chi _{g}(K_{n,n}\square K_{m,m})}$ pour d'arbitraire ${\displaystyle n,m}$.

• Pour une seule arête, on a :

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

• Pour les graphes étoiles, nous avons :

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

• Arbres : ${\displaystyle \chi _{g}(T_{1}\square T_{2})\leq 12.}$
• Roues : ${\displaystyle \chi _{g}(P_{2}\square W_{n})=5}$ si ${\displaystyle n\geq 9.}$
• Graphes bipartis complets : ${\displaystyle \chi _{g}(P_{2}\square K_{m,n})=5}$ si ${\displaystyle m,n\geq 5.}$

Ces questions restent ouvertes à ce jour.

• Supposons qu'Alice possède une stratégie gagnante pour le jeu de coloration des sommets d'un graphe G à k couleurs. En possède-t-elle une pour k+1 couleurs ? ?
  On pourrait s'attendre à ce que la réponses soit « oui », car avoir plus de couleurs semble être un avantage pour Alice. Cependant, aucune preuve formelle n'est connue de cette affirmation.
• Existe-t-il une fonction f telle que, si Alice a une stratégie gagnante pour le jeu de coloration des sommets sur un graphe G avec k couleurs, alors Alice a une stratégie gagnante sur G avec f(k) ? ?
  Affaiblissement de la question précédente.

• Conjecture : Est-ce que si ${\displaystyle F}$ est une forêt, il existe ${\displaystyle F'\subseteq F}$ tel que ${\displaystyle \Delta (F')\leq \chi _{g}(F)}$ et ${\displaystyle \chi _{g}(F')=\chi _{g}(F)}$ ?
• Soit ${\displaystyle {\mathcal {G}}}$ la classe des graphes telle que pour tout ${\displaystyle G\in {\mathcal {G}}}$, il existe ${\displaystyle G'\subseteq G}$ tel que ${\displaystyle \Delta (G')\leq \chi _{g}(G)}$ et ${\displaystyle \chi _{g}(G')=\chi _{g}(G)}$. Quelles familles de graphes sont dans ${\displaystyle {\mathcal {G}}}$ ?

• Est-il vrai que ${\displaystyle \chi _{g}(G)=n+1}$ pour tout hypercube ${\displaystyle Q_{n}}$ ?
  On sait que c'est vrai pour ${\displaystyle n\leq 4}$.

Le jeu de coloration des arêtes, introduit par Lam, Shiu et Zu , est similaire au jeu de coloration des sommets à ceci près qu'Alice et Bob construisent une coloration des arêtes à la place qu'une coloration des sommets. S

Même si ce jeu peut être considéré comme un cas particulier du jeu de coloration des sommets sur les graphes d'arêtes, il est souvent considéré dans la littérature scientifique comme un jeu distinct. L'indice chromatique ludique d'un graphe ${\displaystyle G}$, désigné par ${\displaystyle \chi '_{g}(G)}$ est le nombre minimum de couleurs nécessaires à Alice pour gagner à cette partie sur ${\displaystyle G}$.

Pour chaque graphe G, ${\displaystyle \chi '(G)\leq \chi '_{g}(G)\leq 2\Delta (G)-1}$. Il existe des graphes atteignant ces bornes. Il existe des graphes avec ${\displaystyle \chi '_{g}(G)>1.008\Delta (G)}$ pour des valeurs arbitrairement grandes de ${\displaystyle \Delta (G)}$.

Conjecture

Il existe un ${\displaystyle \epsilon >0}$ tel que, pour tout graphe arbitraire ${\displaystyle G}$, on a ${\displaystyle \chi '_{g}(G)\leq (2-\epsilon )\Delta (G)}$.

• Martin Gardner, Mathematical Games, vol. 23, Scientific American, 1981
• Hans L. Bodlaender, Graph-Theoretic Concepts in Computer Science, vol. 484, Lecture Notes in Computer Science, 1991 (ISBN 978-3-540-53832-5, DOI 10.1007/3-540-53832-1_29), p. 30–40

• Ulrich Faigle, Walter Kern, Henry A. Kierstead et William T. Trotter, « On the Game Chromatic Number of some Classes of Graphs », Ars Combinatoria, vol. 35, n^o 17,‎ 1993, p. 143–150 (lire en ligne)

• Henry A. Kierstead et William T. Trotter, « Planar Graph Coloring with an Uncooperative Partner », Journal of Graph Theory, vol. 18, n^o 6,‎ 1994, p. 564–584 (DOI 10.1002/jgt.3190180605, lire en ligne)

• Thomas Dinski et Xuding Zhu, « A bound for the game chromatic number of graphs », Discrete Mathematics, vol. 196, n^os 1–3,‎ 1999, p. 109–115 (DOI 10.1016/s0012-365x(98)00197-6)

• D. J. Guan et Xuding Zhu, « Game chromatic number of outerplanar graphs », Journal of Graph Theory, vol. 30, n^o 1,‎ 1999, p. 67–70 (DOI 10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m)

• Peter C. B. Lam, Wai C. Shiu et Baogang Xu, « Edge game coloring of graphs », Graph Theory Notes N.Y., vol. 37,‎ 1999, p. 17–19 (lire en ligne)

• Xuding Zhu, « The Game Coloring Number of Planar Graphs », Journal of Combinatorial Theory, Series B, vol. 75, n^o 2,‎ 1999, p. 245–258 (DOI 10.1006/jctb.1998.1878)

• Henry A. Kierstead, « A Simple Competitive Graph Coloring Algorithm », Journal of Combinatorial Theory, Series B, vol. 78, n^o 1,‎ 2000, p. 57–68 (DOI 10.1006/jctb.1999.1927)

• Xuding Zhu, « The game coloring number of pseudo partial k-trees », Discrete Mathematics, vol. 215, n^os 1–3,‎ 2000, p. 245–262 (DOI 10.1016/s0012-365x(99)00237-x)

• Leizhen Cai et Xuding Zhu, « Game Chromatic Index of k-Degenerate Graphs », Journal of Graph Theory, vol. 36, n^o 3,‎ 2001, p. 144–155 (DOI 10.1002/1097-0118(200103)36:3<144::aid-jgt1002>3.0.co;2-f)

• Wenjie He, Xiaoling Hou, Ko-Wei Lih, Jiating Shao, Weifan Wang et Xuding Zhu, « Edge-partitions of planar graphs and their game coloring numbers », Journal of Graph Theory, vol. 41, n^o 4,‎ 2002, p. 307–311 (DOI 10.1002/jgt.10069)

• Peter L. Erdös, Ulrich Faigle, Winfried Hochstättler et Walter Kern, « Note on the game chromatic index of trees », Theoretical Computer Science, vol. 313, n^o 3,‎ 2004, p. 371–376 (DOI 10.1016/j.tcs.2002.10.002, lire en ligne)

• Stephan D. Andres, « The game chromatic index of forests of maximum degree Δ ⩾ 5 », Discrete Applied Mathematics, vol. 154, n^o 9,‎ 2006, p. 1317–1323 (DOI 10.1016/j.dam.2005.05.031)

• Stephan D. Andres, « The game chromatic index of forests of maximum degree Δ ⩾ 5 », Discrete Applied Mathematics, vol. 154, n^o 9,‎ 2006, p. 1317–1323 (DOI 10.1016/j.dam.2005.05.031)

• Tomasz Bartnicki, Jaroslaw Grytczuk, H. A. Kierstead et Xuding Zhu, « The Map-Coloring Game », American Mathematical Monthly, vol. 114, n^o 9,‎ 2007, p. 793–803 (DOI 10.1080/00029890.2007.11920471, lire en ligne)

• Iztok Peterin, « Game chromatic number of Cartesian product graphs », Electronic Notes in Discrete Mathematics, vol. 29,‎ 2007, p. 353–357 (DOI 10.1016/j.endm.2007.07.060)

• Elżbieta Sidorowicz, « The game chromatic number and the game colouring number of cactuses », Information Processing Letters, vol. 102, n^o 4,‎ 2007, p. 147–151 (DOI 10.1016/j.ipl.2006.12.003, lire en ligne)

• Tomasz Bartnicki et Jarosław Grytczuk, « A Note on the Game Chromatic Index of Graphs », Graphs and Combinatorics, vol. 24, n^o 2,‎ 2008, p. 67–70 (DOI 10.1007/s00373-008-0774-z)

• Andrew Beveridge, Tom Bohman, Alan Frieze et Oleg Pikhurko, « Game chromatic index of graphs with given restrictions on degrees », Theoretical Computer Science, vol. 407, n^os 1–3,‎ 2008, p. 242–249 (DOI 10.1016/j.tcs.2008.05.026)

• Xuding Zhu, « Refined activation strategy for the marking game », Journal of Combinatorial Theory, Series B, vol. 98, n^o 1,‎ 2008, p. 1–18 (DOI 10.1016/j.jctb.2007.04.004)

• Stefan D. Andres, « The incidence game chromatic number », Discrete Applied Mathematics, vol. 157, n^o 9,‎ 2009, p. 1980–1987 (DOI 10.1016/j.dam.2007.10.021)

• Stefan D. Andres, « Erratum to: The incidence game chromatic number », Discrete Applied Mathematics, vol. 158, n^o 6,‎ 2009, p. 728 (DOI 10.1016/j.dam.2009.11.017)

• André Raspaud et Jiaojiao Wu, « Game chromatic number of toroidal grids », Information Processing Letters, vol. 109, n^os 21–22,‎ 2009, p. 1183–1186 (DOI 10.1016/j.ipl.2009.08.001)

• Charmaine Sia, « The Game Chromatic Number of Some Families of Cartesian Product Graphs », AKCE International Journal of Graphs and Combinatorics, vol. 6, n^o 2,‎ 2009, p. 315–327 (lire en ligne)

• Konstanty Junosza-Szaniawski et Łukasz Rożej, « Game chromatic number of graphs with locally bounded number of cycles », Information Processing Letters, vol. 110, n^o 17,‎ 2010, p. 757–760 (DOI 10.1016/j.ipl.2010.06.004, lire en ligne)

• John Y. Kim, « The incidence game chromatic number of paths and subgraphs of wheels », Discrete Applied Mathematics, vol. 159, n^o 8,‎ 2011, p. 683–694 (DOI 10.1016/j.dam.2010.01.001)

• Clément Charpentier et Éric Sopena, Combinatorial Algorithms, vol. 8288, 2013, 106–114 p. (ISBN 978-3-642-45277-2, DOI 10.1007/978-3-642-45278-9_10), « Incidence Coloring Game and Arboricity of Graphs »

• Wai H. Chan et Ge Nong, « The game chromatic index of some trees of maximum degree 4 », Discrete Applied Mathematics, vol. 170,‎ 2014, p. 1–6 (DOI 10.1016/j.dam.2014.01.003)

• Yosuke Sekigushi, « The game coloring number of planar graphs with a given girth », Discrete Mathematics, vol. 300,‎ 2014, p. 11–16 (DOI 10.1016/j.disc.2014.04.011)

• Clément Charpentier et Éric Sopena, « The incidence game chromatic number of (a,d)-decomposable graphs », Journal of Discrete Algorithms, vol. 31,‎ 2014, p. 14–25 (DOI 10.1016/j.jda.2014.10.001)

• Eurinardo Costa, Victor Lage Pessoa, Ronan Soares et Rudini Sampaio, « PSPACE-completeness of two graph coloring games », Theoretical Computer Science, vol. 824-825,‎ 2020, p. 36–45 (DOI 10.1016/j.tcs.2020.03.022)

• Peter Bradshaw, « Graph colorings with restricted bicolored subgraphs: II. The graph coloring game », Journal of Graph Theory, vol. 100, n^o 2,‎ 2021, p. 371–383 (DOI 10.1002/jgt.22786)

• Portail des mathématiques