The coloring game is a two-player competition played on a graph. Alice and Bob take turns picking uncolored vertices and assigning them a color from a fixed set of colors, with the rule that no two neighboring vertices can share the same color. Alice wants to successfully color the entire graph, while Bob tries to create a situation where some vertex cannot be colored without violating the rules. The game chromatic number of a graph is the smallest number of colors that guarantees Alice a winning strategy, no matter how Bob plays.
Complete multipartite graphs are a specific and well-studied family of graphs. You build one by dividing vertices into groups called "parts," and then connecting every vertex in one group to every vertex in every other group, while leaving vertices within the same group unconnected. The researchers focused on cases where each part is either a single vertex (a singleton) or a group of at least four vertices, avoiding the messy middle cases of sizes two and three.
The main contribution of the paper is an explicit formula for the game chromatic number of these graphs. The formula depends on how many singleton parts there are and on the sizes of the larger parts, arranged in a particular order. This builds on earlier work by Obszarski and colleagues, extending their results to cover this broader class of graphs and giving a clean, computable answer to what had previously been an open question for this family.