Jeu de coloration de graphe

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}$.