On the path-avoidance vertex-coloring game (Q640416)

Summary: For any graph \(F\) and any integer \(r\geq 2\), the online vertex-Ramsey density of \(F\) and \(r\), denoted \(m^*(F,r)\), is a parameter defined via a deterministic two-player Ramsey-type game (Painter vs. Builder). This parameter was introduced in a recent paper [arXiv:1103.5849], where it was shown that the online vertex-Ramsey density determines the threshold of a similar probabilistic one-player game (Painter vs. the binomial random graph \(G_{n,p})\). For a large class of graphs \(F\), including cliques, cycles, complete bipartite graphs, hypercubes, wheels, and stars of arbitrary size, a simple greedy strategy is optimal for Painter and closed formulas for \(m^*(F,r)\) are known. In this work we show that for the case where \(F=P_\ell\) is a long path, the picture is very different. It is not hard to see that \(m^*(P_\ell,r)= 1-1/k^*(P_\ell,r)\) for an appropriately defined integer \(k^*(P_\ell,r)\), and that the greedy strategy gives a lower bound of \(k^*(P_\ell,r)\geq\ell^r\). We construct and analyze Painter strategies that improve on this greedy lower bound by a factor polynomial in \(\ell\), and we show that no superpolynomial improvement is possible.