{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:06:45Z","timestamp":1777457205756,"version":"3.51.4"},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2018,7,24]],"date-time":"2018-07-24T00:00:00Z","timestamp":1532390400000},"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,3]]},"abstract":"<jats:p>For an integer <jats:italic>q<\/jats:italic> \u2a7e 2 and an even integer <jats:italic>d<\/jats:italic>, consider the graph obtained from a large complete <jats:italic>q<\/jats:italic>-ary tree by connecting with an edge any two vertices at distance exactly <jats:italic>d<\/jats:italic> in the tree. This graph has clique number <jats:italic>q<\/jats:italic> + 1, and the purpose of this short note is to prove that its chromatic number is \u0398((<jats:italic>d<\/jats:italic> log <jats:italic>q<\/jats:italic>)\/log <jats:italic>d<\/jats:italic>). It was not known that the chromatic number of this graph grows with <jats:italic>d<\/jats:italic>. As a simple corollary of our result, we give a negative answer to a problem of van den Heuvel and Naserasr, asking whether there is a constant <jats:italic>C<\/jats:italic> such that for any odd integer <jats:italic>d<\/jats:italic>, any planar graph can be coloured with at most <jats:italic>C<\/jats:italic> colours such that any pair of vertices at distance exactly <jats:italic>d<\/jats:italic> have distinct colours. Finally, we study interval colouring of trees (where vertices at distance at least <jats:italic>d<\/jats:italic> and at most <jats:italic>cd<\/jats:italic>, for some real <jats:italic>c<\/jats:italic> &gt; 1, must be assigned distinct colours), giving a sharp upper bound in the case of bounded degree trees.<\/jats:p>","DOI":"10.1017\/s0963548318000378","type":"journal-article","created":{"date-parts":[[2018,7,24]],"date-time":"2018-07-24T03:09:17Z","timestamp":1532401757000},"page":"177-186","source":"Crossref","is-referenced-by-count":9,"title":["Exact Distance Colouring in Trees"],"prefix":"10.1017","volume":"28","author":[{"given":"NICOLAS","family":"BOUSQUET","sequence":"first","affiliation":[]},{"given":"LOUIS","family":"ESPERET","sequence":"additional","affiliation":[]},{"given":"ARARAT","family":"HARUTYUNYAN","sequence":"additional","affiliation":[]},{"given":"R\u00c9MI","family":"DE JOANNIS DE VERCLOS","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,7,24]]},"reference":[{"key":"S0963548318000378_ref6","unstructured":"Parlier H. and Petit C. (2017) Chromatic numbers for the hyperbolic plane and discrete analogs. arXiv:1701.08648"},{"key":"S0963548318000378_ref2","unstructured":"van den Heuvel J. , Kierstead H. A. and Quiroz D. (2016) Chromatic numbers of exact distance graphs. J. Combin. Theory Ser. B. arXiv:1612.02160"},{"key":"S0963548318000378_ref8","unstructured":"Quiroz D. (2017) Colouring exact distance graphs of chordal graphs. arXiv:1703.07008"},{"key":"S0963548318000378_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-015-1569-7"},{"key":"S0963548318000378_ref7","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.2016.65.5842"},{"key":"S0963548318000378_ref3","first-page":"117","article-title":"Coloring distance graphs: A few answers and many questions","volume":"24","author":"Kloeckner","year":"2015","journal-title":"Geombinatorics"},{"key":"S0963548318000378_ref1","unstructured":"de Grey A. D. N. J. (2018) The chromatic number of the plane is at least 5. arXiv:1804.02385"},{"key":"S0963548318000378_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000378","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T15:03:28Z","timestamp":1555081408000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000378\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,24]]},"references-count":8,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["S0963548318000378"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000378","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,24]]}}}