Çizgelerin oyun kromatik sayıları

Bir $G$ çizgesinin oyun kromatik sayısı, ilk olarak Bodlaender tarafından iki kişilik bir boyama oyunu yardımıyla tanımlanmıştır. $G$ sonlu bir çizge ve $X$ bir renkler kümesi olsun. Genellikle Alice ve Bob olarak adlandırılan iki oyuncu, ilk olarak Alice başlamak üzere sırayla $X$ kümesinden seçtikleri renklerle, komşu köşe noktalar farklı renklerde olacak şekilde çizgenin köşe noktalarını boyarlar. Eğer çizgenin tüm köşe noktaları bu şekilde boyanabilirse oyunu Alice kazanır. Ancak, oyunun herhangi bir aşamasında $X$ kümesinden seçilen renklerle boyanan noktalara komşu ve boyanmamış bir nokta kalırsa, oyunu Bob kazanır. Bir $G$ çizgesinin oyun kromatik sayısı $\chi_g(G)$, oyuncular optimal stratejileri ile oynadıklarında Alice'in her zaman kazanabildiği bir stratejisinin olduğu $X$ kümesindeki minimum renk sayısı olarak tanımlanır. Bu çalışmada, çeşitli çizge ailelerinde ve belirli çizgelerin Kartezyen çarpımlarında oyun kromatik sayıları incelenmiş, mevcut araştırmalardan elde edilen sonuçlar derlenerek sunulmuştur.