{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T22:56:39Z","timestamp":1763765799229},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2009,9,9]],"date-time":"2009-09-09T00:00:00Z","timestamp":1252454400000},"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":[[2010,1]]},"abstract":"<jats:p>We consider the <jats:italic>t<\/jats:italic>-improper chromatic number of the Erd\u0151s\u2013R\u00e9nyi random graph <jats:italic>G<jats:sub>n,p<\/jats:sub><\/jats:italic>. The <jats:italic>t<\/jats:italic>-improper chromatic number \u03c7<jats:sup><jats:italic>t<\/jats:italic><\/jats:sup>(<jats:italic>G<\/jats:italic>) is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most <jats:italic>t<\/jats:italic>. If <jats:italic>t<\/jats:italic> = 0, then this is the usual notion of proper colouring. When the edge probability <jats:italic>p<\/jats:italic> is constant, we provide a detailed description of the asymptotic behaviour of \u03c7<jats:sup><jats:italic>t<\/jats:italic><\/jats:sup>(<jats:italic>G<jats:sub>n,p<\/jats:sub><\/jats:italic>) over the range of choices for the growth of <jats:italic>t<\/jats:italic> = <jats:italic>t<\/jats:italic>(<jats:italic>n<\/jats:italic>).<\/jats:p>","DOI":"10.1017\/s0963548309990216","type":"journal-article","created":{"date-parts":[[2009,9,9]],"date-time":"2009-09-09T04:52:16Z","timestamp":1252471936000},"page":"87-98","source":"Crossref","is-referenced-by-count":12,"title":["The <i>t<\/i>-Improper Chromatic Number of Random Graphs"],"prefix":"10.1017","volume":"19","author":[{"given":"ROSS J.","family":"KANG","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"COLIN","family":"McDIARMID","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,9,9]]},"reference":[{"key":"S0963548309990216_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5320-4"},{"key":"S0963548309990216_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T"},{"key":"S0963548309990216_ref8","first-page":"79","article-title":"Defective list colorings of planar graphs","volume":"25","author":"Eaton","year":"1999","journal-title":"Bull. Inst. Combin. Appl."},{"key":"S0963548309990216_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548309990216_ref9","unstructured":"[9] Fountoulakis N. , Kang R. J. and McDiarmid C. (2008) The t-stability number of a random graph. Submitted; arxiv.0809.0141: [math.CO]."},{"key":"S0963548309990216_ref12","first-page":"205","volume-title":"Proc. Sundance Conference on Combinatorics and Related Topics","author":"Harary","year":"1985"},{"key":"S0963548309990216_ref1","first-page":"33","volume-title":"Proc. Sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing","author":"Andrews","year":"1985"},{"key":"S0963548309990216_ref14","unstructured":"[14] Kang R. J. (2008) Improper colourings of graphs. PhD thesis, University of Oxford. ora.ouls.ox.ac.uk\/objects\/uuid:a93d8303-0eeb-4d01-9b77-364113b81a63."},{"key":"S0963548309990216_ref11","first-page":"127","volume-title":"Graphs and Applications","author":"Harary","year":"1985"},{"key":"S0963548309990216_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548309990216_ref20","first-page":"175","volume-title":"Random Graphs '87","author":"Matula","year":"1990"},{"key":"S0963548309990216_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100051124"},{"key":"S0963548309990216_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"S0963548309990216_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/0405006"},{"key":"S0963548309990216_ref17","first-page":"237","article-title":"On decompositions of graphs","volume":"1","author":"Lov\u00e1sz","year":"1966","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548309990216_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"S0963548309990216_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100207"},{"key":"S0963548309990216_ref4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s004930070019","article-title":"The structure of hereditary properties and colourings of random graphs","volume":"20","author":"Bollob\u00e1s","year":"2000","journal-title":"Combinatorica."},{"key":"S0963548309990216_ref15","first-page":"419","volume-title":"Proc 4th European Conference on Combinatorics, Graph Theory and Applications","author":"Kang","year":"2007"},{"key":"S0963548309990216_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375472"},{"key":"S0963548309990216_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.070"},{"key":"S0963548309990216_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003752"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990216","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T17:04:27Z","timestamp":1556471067000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990216\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,9]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["S0963548309990216"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990216","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,9]]}}}