Weak acyclic coloring and asymmetric coloring games (Q2488942)

From the author's abstract: We introduce the notion of weak acyclic coloring of a graph. This is a relaxation of the usual notion of acyclic coloring which is often sufficient for applications. We then use this concept to analyze the \((a,b)\)-coloring game. This game is played on a finite graph \(G\) using a set of colors \(X\), by two players Alice and Bob with Alice playing first. On each turn Alice (Bob) chooses \(a\) (\(b\)) uncolored vertices and properly colors them with colors from \(X\). Alice wins if the players eventually create a proper coloring of \(G\); otherwise Bob wins when one of the players has no legal move. The \((a,b)\)-game chromatic number of \(G\), denoted \((a,b)\)-\(\chi_g(G)\), is the least integer \(t\) such that Alice has a winning strategy when the game is played on \(G\) using \(t\) colors. We show that if the weak acyclic chromatic number of \(G\) is at most \(k\), then \((2,1)\)-\(\chi_g(G) \leq (k^2 + 3k)/2\).