{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:53Z","timestamp":1753893833953,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.37236\/650","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T03:43:13Z","timestamp":1578714193000},"source":"Crossref","is-referenced-by-count":3,"title":["On the Path-Avoidance Vertex-Coloring Game"],"prefix":"10.37236","volume":"18","author":[{"given":"Torsten","family":"M\u00fctze","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reto","family":"Sp\u00f6hel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2011,8,12]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v18i1p163\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v18i1p163\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T23:07:14Z","timestamp":1579302434000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v18i1p163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,12]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2011,1,5]]}},"URL":"https:\/\/doi.org\/10.37236\/650","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2011,8,12]]},"article-number":"P163"}}