{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T17:06:58Z","timestamp":1765040818976},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2018,5,9]],"date-time":"2018-05-09T00:00:00Z","timestamp":1525824000000},"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":[[2018,11]]},"abstract":"<jats:p>For fixed integers <jats:italic>p<\/jats:italic> and <jats:italic>q<\/jats:italic>, let <jats:italic>f<\/jats:italic>(<jats:italic>n<\/jats:italic>,<jats:italic>p<\/jats:italic>,<jats:italic>q<\/jats:italic>) denote the minimum number of colours needed to colour all of the edges of the complete graph <jats:italic>K<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> such that no clique of <jats:italic>p<\/jats:italic> vertices spans fewer than <jats:italic>q<\/jats:italic> distinct colours. Any edge-colouring with this property is known as a (<jats:italic>p<\/jats:italic>,<jats:italic>q<\/jats:italic>)-colouring. We construct an explicit (5,5)-colouring that shows that <jats:italic>f<\/jats:italic>(<jats:italic>n<\/jats:italic>,5,5) \u2264 <jats:italic>n<\/jats:italic><jats:sup>1\/3 + <jats:italic>o<\/jats:italic>(1)<\/jats:sup> as <jats:italic>n<\/jats:italic> \u2192 \u221e. This improves upon the best known probabilistic upper bound of <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>1\/2<\/jats:sup>) given by Erd\u0151s and Gy\u00e1rf\u00e1s, and comes close to matching the best known lower bound \u03a9(<jats:italic>n<\/jats:italic><jats:sup>1\/3<\/jats:sup>).<\/jats:p>","DOI":"10.1017\/s0963548318000172","type":"journal-article","created":{"date-parts":[[2018,5,9]],"date-time":"2018-05-09T01:52:03Z","timestamp":1525830723000},"page":"892-912","source":"Crossref","is-referenced-by-count":6,"title":["A (5,5)-Colouring of <i>K<\/i><sub><i>n<\/i><\/sub> with Few Colours"],"prefix":"10.1017","volume":"27","author":[{"given":"ALEX","family":"CAMERON","sequence":"first","affiliation":[]},{"given":"EMILY","family":"HEATH","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,5,9]]},"reference":[{"key":"S0963548318000172_ref12","first-page":"529","article-title":"Bombieri's theorem in short intervals","volume":"11","author":"Perelli","year":"1984","journal-title":"Annali della Scuola Normale Superiore di Pisa\u2013Classe di Scienze"},{"key":"S0963548318000172_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01195000"},{"key":"S0963548318000172_ref6","first-page":"1","article-title":"Solved and unsolved problems in combinatorics and combinatorial number theory","volume":"2","author":"Erd\u0151s","year":"1981","journal-title":"Europ. J. Combin."},{"key":"S0963548318000172_ref3","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdu049"},{"key":"S0963548318000172_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009822"},{"key":"S0963548318000172_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21876"},{"key":"S0963548318000172_ref2","volume-title":"Linear Algebra Methods in Combinatorics: With Applications to Geometry and Computer Science","author":"Babai","year":"1992"},{"key":"S0963548318000172_ref5","first-page":"183","volume-title":"Recent Advances in Graph Theory","author":"Erd\u0151s","year":"1975"},{"key":"S0963548318000172_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070016"},{"key":"S0963548318000172_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0019-6"},{"key":"S0963548318000172_ref8","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1710"},{"key":"S0963548318000172_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00052-2"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000172","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T18:46:13Z","timestamp":1555094773000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000172\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,9]]},"references-count":12,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["S0963548318000172"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000172","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,9]]}}}