Two-Turn Assymetric Graph Coloring Games

期刊论文
发表日期：

2025年9月26日

查看全文

Eder Figueiredo,
Vinicius Fernandes dos Santos

摘要

Let G be a graph, a and b nonnegative integers, the (a, b)-coloring game is an asymmetric, two-player game played on G, where Alice and Bob alternately choose a and b uncolored vertices of G, respectively, and assign colors to them, while ensuring that no pair of adjacent vertices share the same color. We study Two-Turn Graph Coloring Game, a special case where \(a+b = |V(G)|\) , meaning that the game ends after each player has played exactly once. First, we characterize the graphs in which Alice has a winning strategy when \(a\le 1\) . We then present a polynomial-time algorithm to decide whether Alice has a winning strategy in the \((k, |V(G)|-k)\) -coloring game for any fixed k. Finally, we prove that deciding whether Alice has a winning strategy on a Two-Turn Graph Coloring Game is NP-complete.