Graphenfärbungsprobleme treten in vielen Anwendungen auf, wie zum Beispiel bei der Funkfrequenzzuweisung oder Stundenplanproblemen oder, allgemeiner, bei Problemen, bei denen verschiedene Ressourcen miteinander in Konflikt stehen. Meist sind aber keine effizienten Lösungsverfahren bekannt. Eine Klasse von Graphen, bei denen das Färben gutartig ist, sind die sogenannten perfekten Graphen. Diese wurden 2006 von Chudnovsky, Robertson, Seymour und Thomas durch einen Beweis einer jahrzehntelang offenen Vermutung von Berge mittels verbotener induzierter Teilgraphen klassifiziert. Im Gegensatz zu diesen Problemen, deren Lösung eine zentrale Instanz vornehmen kann, stehen Probleme, in denen anarchistische Elemente, die eigene Interessen verfolgen, die Lösungsfindung stören dürfen. Letztere stellen nichtkooperative Spiele dar. In einem mathematisch sehr vereinfachten Modell färben zwei Spieler abwechselnd bislang ungefärbte Knoten eines gegebenen Graphen mit Farben einer vorgegebenen Farbmenge, so dass benachbarte Knoten verschiedenfarbig gefärbt sind. Wenn das Spiel