{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:08:27Z","timestamp":1775052507265,"version":"3.50.1"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T00:00:00Z","timestamp":1552608000000},"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":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The strong chromatic number <jats:italic>\u03c7<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) of a graph <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices is the least number <jats:italic>r<\/jats:italic> with the following property: after adding <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548318000561_inline1\"\/><jats:tex-math>$r\\lceil n\/r\\rceil-n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> isolated vertices to <jats:italic>G<\/jats:italic> and taking the union with any collection of spanning disjoint copies of <jats:italic>K<jats:sub>r<\/jats:sub><\/jats:italic> in the same vertex set, the resulting graph has a proper vertex colouring with <jats:italic>r<\/jats:italic> colours. We show that for every <jats:italic>c<\/jats:italic> &gt; 0 and every graph <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices with \u0394(<jats:italic>G<\/jats:italic>) \u2265 <jats:italic>cn<\/jats:italic>, <jats:italic>\u03c7<\/jats:italic><jats:sub>s<\/jats:sub>(<jats:italic>G<\/jats:italic>) \u2264 (2+<jats:italic>o<\/jats:italic>(1))\u0394(<jats:italic>G<\/jats:italic>), which is asymptotically best possible.<\/jats:p>","DOI":"10.1017\/s0963548318000561","type":"journal-article","created":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T06:13:39Z","timestamp":1552630419000},"page":"768-776","source":"Crossref","is-referenced-by-count":4,"title":["An asymptotic bound for the strong chromatic number"],"prefix":"10.1017","volume":"28","author":[{"given":"Allan","family":"Lo","sequence":"first","affiliation":[]},{"given":"Nicol\u00e1s","family":"Sanhueza-Matamala","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,3,15]]},"reference":[{"key":"S0963548318000561_ref19","unstructured":"[19] Pippenger, N. Unpublished."},{"key":"S0963548318000561_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007042"},{"key":"S0963548318000561_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2006.11.006"},{"key":"S0963548318000561_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831200048X"},{"key":"S0963548318000561_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003106"},{"key":"S0963548318000561_ref14","first-page":"277","article-title":"Factors of r-partite graphs and bounds for the strong chromatic number","volume":"95","author":"Johansson","year":"2010","journal-title":"Ars Combin."},{"key":"S0963548318000561_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24298-9_9"},{"key":"S0963548318000561_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20300"},{"key":"S0963548318000561_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006157"},{"key":"S0963548318000561_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2086-y"},{"key":"S0963548318000561_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02783300"},{"key":"S0963548318000561_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548318000561_ref15","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2761"},{"key":"S0963548318000561_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60406-5_13"},{"key":"S0963548318000561_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90588-7"},{"key":"S0963548318000561_ref21","first-page":"347","volume-title":"Combinatorics: Paul Erd\u00f6s is Eighty","volume":"1","author":"Sachs","year":"1993"},{"key":"S0963548318000561_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/050633056"},{"key":"S0963548318000561_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004758"},{"key":"S0963548318000561_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030102"},{"key":"S0963548318000561_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/0403018"},{"key":"S0963548318000561_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01793010"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T03:51:27Z","timestamp":1568173887000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000561\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,15]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S0963548318000561"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000561","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,15]]}}}