go-v.orgdoi

On the Path-Avoidance Vertex-Coloring Game

Torsten Mütze, Reto Spöhel · The Electronic Journal of Combinatorics · 2011

  • DOI 10.37236/650
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2011

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2011

Abstract

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.

Open the resolved locator · 10.37236/650

Metadata licence: OpenAlex metadata (CC0)