{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T20:58:13Z","timestamp":1770325093724,"version":"3.49.0"},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>The game colouring number gcol(<jats:italic>G<\/jats:italic>) of a graph<jats:italic>G<\/jats:italic>is the least<jats:italic>k<\/jats:italic>such that, if two players take turns choosing the vertices of a graph, then either of them can ensure that every vertex has fewer than<jats:italic>k<\/jats:italic>neighbours chosen before it, regardless of what choices the other player makes. Clearly gcol(<jats:italic>G<\/jats:italic>) \u2264 \u0394(<jats:italic>G<\/jats:italic>)+1. Sauer and Spencer [20] proved that if two graphs<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>and<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>on<jats:italic>n<\/jats:italic>vertices satisfy 2\u0394(<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>)\u0394(<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>) &lt;<jats:italic>n<\/jats:italic>then they pack,<jats:italic>i.e<\/jats:italic>., there is an embedding of<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>into the complement of<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>. We improve this by showing that if (gcol(<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>)\u22121)\u0394(<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>)+(gcol(<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>)\u22121)\u0394(<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>) &lt;<jats:italic>n<\/jats:italic>then<jats:italic>G<\/jats:italic><jats:sub>1<\/jats:sub>and<jats:italic>G<\/jats:italic><jats:sub>2<\/jats:sub>pack. To our knowledge this is the first application of colouring games to a non-game problem.<\/jats:p>","DOI":"10.1017\/s0963548309009973","type":"journal-article","created":{"date-parts":[[2009,5,21]],"date-time":"2009-05-21T10:32:03Z","timestamp":1242901923000},"page":"765-774","source":"Crossref","is-referenced-by-count":21,"title":["Efficient Graph Packing via Game Colouring"],"prefix":"10.1017","volume":"18","author":[{"given":"H. A.","family":"KIERSTEAD","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. V.","family":"KOSTOCHKA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,9,1]]},"reference":[{"key":"S0963548309009973_ref16","doi-asserted-by":"publisher","DOI":"10.1023\/B:ORDE.0000026489.93166.cb"},{"key":"S0963548309009973_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00237-X"},{"key":"S0963548309009973_ref10","doi-asserted-by":"crossref","unstructured":"[10] Gardner M. (1981) Mathematical games. Scientific American (April 1981), 23.","DOI":"10.1038\/scientificamerican1081-23"},{"key":"S0963548309009973_ref1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054191000091"},{"key":"S0963548309009973_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00197-6"},{"key":"S0963548309009973_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"S0963548309009973_ref24","doi-asserted-by":"crossref","unstructured":"[24] Zhu X. Colouring graphs with bounded generalized colouring number. Discrete Math., to appear.","DOI":"10.1016\/j.disc.2008.03.024"},{"key":"S0963548309009973_ref15","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s00373-002-0489-5","article-title":"Marking games and the oriented game chromatic number of partial k-trees","volume":"19","author":"Kierstead","year":"2003","journal-title":"Graphs Combin."},{"key":"S0963548309009973_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0732-1"},{"key":"S0963548309009973_ref11","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1927"},{"key":"S0963548309009973_ref21","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1878"},{"key":"S0963548309009973_ref14","article-title":"Competitive colorings of oriented graphs","volume":"8","author":"Kierstead","year":"2001","journal-title":"Electron. J. Combin."},{"key":"S0963548309009973_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90030-8"},{"key":"S0963548309009973_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006887"},{"key":"S0963548309009973_ref6","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1012"},{"key":"S0963548309009973_ref19","doi-asserted-by":"crossref","first-page":"#14","DOI":"10.37236\/1613","article-title":"On the oriented game chromatic number","volume":"8","author":"Ne\u0161et\u0159il","year":"2001","journal-title":"Electron. J. Combin."},{"key":"S0963548309009973_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90119-8"},{"key":"S0963548309009973_ref12","unstructured":"[12] Kierstead H. A. , Mohar B. , \u0160pacapan S. , Yang D. and Zhu X. The two-coloring number and degenerate colorings of planar graphs. Submitted."},{"key":"S0963548309009973_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.04.004"},{"key":"S0963548309009973_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90005-9"},{"key":"S0963548309009973_ref4","unstructured":"[4] Burr S. A. and Erd\u0151s P. (1975) On the magnitude of generalized Ramsey numbers. In Infinite and Finite Sets (A. Hajnal, R. Rado and V. T. S\u00f3s, eds), Colloq. Math. Soc. Janos Bolyai, Vol. 1, North-Holland."},{"key":"S0963548309009973_ref9","first-page":"143","article-title":"On the game chromatic number of some classes of graphs","volume":"35","author":"Faigle","year":"1993","journal-title":"Ars Combin."},{"key":"S0963548309009973_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90037-0"},{"key":"S0963548309009973_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180605"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309009973","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T14:08:08Z","timestamp":1589810888000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309009973\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["S0963548309009973"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309009973","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]}}}