Bradley University1, Mathematics, Peoria, IL 61606 Linfield College2, Mathematics, McMinnville, OR 97128 University of Rochester3, Mathematics, Rochester, NY 14627 McMinville School District4, McMinville, OR 97128
Let G be a finite graph, r a positive integer, and d a non-negative integer. We consider a game in which two players, Alice and Bob, take turns coloring the vertices of G from a set of r colors. Every vertex with a given color can be adjacent to at most d vertices with the same color. Alice wins if every vertex of G is eventually colored; otherwise Bob wins. The least r such that Alice has a winning strategy in this game is called the d-relaxed game chromatic number of G. Although relaxed game chromatic numbers are often difficult to precisely determine, we can often make progress by imposing restrictions on d and G. In this talk, we consider the case where G is a complete multipartite graph and d < 3, focusing on our classification of the 1-relaxed game chromatic number for all such graphs.
[Abstract (DOCX)]