vignette|300x300px|Le jeu de coloration sur un graphe oppose Alice et Bob. Alice colorie les sommets marqués « A », et Bob les sommets marqués « B ». Les joueurs colorient chacun leur tour (en commençant par Alice) les sommets du graphe. Si le graphe est entièrement colorié à la fin, Alice gagne. Si, à un moment donné, un sommet devient impossible à colorier correctement, Bob gagne.Le nombre chromatique ludique est le nombre minimum de couleurs nécessaires à Alice pour gagner au jeu de coloriage des sommets sur .

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.

Jeu de coloriage de sommets Le jeu de coloriage de sommets a été introduit en 1981 par Steven Brams et redécouvert dix ans plus tard par Bodlaender. Ses règles sont les suivantes :

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

Le nombre chromatique ludique d'un graphe , noté est le nombre minimum de couleurs nécessaires à Alice pour posséder une stratégie gagnante. De façon évidente, pour tout graphe , on a , où est le nombre chromatique de et son degré maximal.

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

Relation avec d'autres notions Coloration acyclique Tout graphe avec nombre chromatique acyclique a .

Arêtes avec peu de cycles Si chaque arête d'un graphe appartient à au plus cycles, puis .

Classes de graphes Pour une classe de graphes, on appelle le plus petit entier tel que chaque graphe de vérifie.

Forêts : Des critères simples sont connus pour déterminer le nombre chromatique de jeu d'une forêt sans sommet de degré 3. Cactus : . Graphes planaires externes : . Graphes planaires : . Graphes planaires de maille donnée : , , , . Grilles toroïdales : . k-arbres : . Graphes d'intervalles : , où est pour un graphe la taille de sa plus grande clique.

Produits cartésiens Le nombre chromatique ludique du produit cartésien n'est pas borné par une fonction de et . En particulier, le nombre chromatique ludique de tout graphe biparti complet est égal à 3, mais il n'y a pas de limite supérieure pour pour d'arbitraire .

Pour une seule arête, on a :

Pour les graphes étoiles, nous avons :

Arbres : Roues : si Graphes bipartis complets : si

Problèmes ouverts Ces questions restent ouvertes à ce jour.

Plus de couleurs pour Alice

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.

Réduction du degré maximum

Conjecture : Est-ce que si est une forêt, il existe tel que et ? Soit la classe des graphes telle que pour tout , il existe tel que et . Quelles familles de graphes sont dans ?

Hypercubes

Est-il vrai que pour tout hypercube ? On sait que c'est vrai pour .

Jeu de coloration des arêtes 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 , désigné par est le nombre minimum de couleurs nécessaires à Alice pour gagner à cette partie sur .

Cas général Pour chaque graphe G, . Il existe des graphes atteignant ces bornes. Il existe des graphes avec pour des valeurs arbitrairement grandes de .

Conjecture Il existe un tel que, pour tout graphe arbitraire , on a .

Notes et références

Bibliographie

Catégorie:Coloration d'un graphe Catégorie:Pages avec des traductions non relues