Results on the Connected Greedy Coloring Game
摘要
The graph coloring game is a game propose by Bodlaender in 1991 that consists in, given a graph G and a set C of integers (the colors), two players called Alice and Bob, alternate turns, starting with Alice, selecting an uncolored vertex v and a color in C to color v such that the chosen color is not already used in any of the neighbors of v. Alice wins if she colors all vertices of G, otherwise, Bob wins. Since then, this game and several of its variants have been extensively study. In 2023, Havet and Zhu introduced the greedy variant, in which the players choose only a vertex, the color is always the least possible color so to not violate the game rules. In 2020, Chapentier et al. introduced the connected variant, where the set of colored vertices must always induce a connected subgraph. In 2023, Lima et al. introduced the connected greedy variant, that combines the constraints from both variants, proving several results about the parameter