{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T02:35:06Z","timestamp":1778553306789,"version":"3.51.4"},"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>When graph Ramsey theory is viewed as a game, \"Painter\" 2-colors the edges of a graph presented by \"Builder\".  Builder wins if every coloring has a monochromatic copy of a fixed graph $G$.  In the on-line version, iteratively, Builder presents one edge and Painter must color it.  Builder must keep the presented graph in a class ${\\cal H}$.  Builder wins the game $(G,{\\cal H})$ if a monochromatic copy of $G$ can be forced.  The on-line degree Ramsey number $\\mathring {R}_\\Delta(G)$ is the least $k$ such that Builder wins $(G,{\\cal H})$ when ${\\mathcal H}$ is the class of graphs with maximum degree at most $k$. Our results include: 1) $\\mathring {R}_\\Delta(G)\\!\\le\\!3$ if and only if $G$ is a linear forest or each component lies inside $K_{1,3}$. 2) $\\mathring {R}_\\Delta(G)\\ge \\Delta(G)+t-1$, where $t=\\max_{uv\\in E(G)}\\min\\{d(u),d(v)\\}$. 3) $\\mathring {R}_\\Delta(G)\\le d_1+d_2-1$ for a tree $G$, where $d_1$ and $d_2$ are two largest vertex degrees. 4) $4\\le \\mathring {R}_\\Delta(C_n)\\le 5$, with $\\mathring {R}_\\Delta(C_n)=4$ except for finitely many odd values of $n$. 5) $\\mathring {R}_\\Delta(G)\\le6$ when $\\Delta(G)\\le 2$.   The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class.  The upper bounds use a result showing that Builder may assume that Painter plays \"consistently\".<\/jats:p>","DOI":"10.37236\/623","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T03:46:26Z","timestamp":1578714386000},"source":"Crossref","is-referenced-by-count":13,"title":["On-line Ramsey Theory for Bounded Degree Graphs"],"prefix":"10.37236","volume":"18","author":[{"given":"Jane","family":"Butterfield","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tracy","family":"Grauman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William B.","family":"Kinnersley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin G.","family":"Milans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Stocker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas B.","family":"West","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2011,7,1]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v18i1p136\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v18i1p136\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T23:08:33Z","timestamp":1579302513000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v18i1p136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,1]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2011,1,5]]}},"URL":"https:\/\/doi.org\/10.37236\/623","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,1]]},"article-number":"P136"}}