{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:21:54Z","timestamp":1778664114539,"version":"3.51.4"},"reference-count":9,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2013,11,14]],"date-time":"2013-11-14T00:00:00Z","timestamp":1384387200000},"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":[[2014,1]]},"abstract":"<jats:p>We consider two graph colouring problems in which edges at distance at most <jats:italic>t<\/jats:italic> are given distinct colours, for some fixed positive integer <jats:italic>t<\/jats:italic>. We obtain two upper bounds for the distance-<jats:italic>t<\/jats:italic> chromatic index, the least number of colours necessary for such a colouring. One is a bound of (2-\u03b5)\u0394<jats:sup><jats:italic>t<\/jats:italic><\/jats:sup> for graphs of maximum degree at most \u0394, where \u03b5 is some absolute positive constant independent of <jats:italic>t<\/jats:italic>. The other is a bound of <jats:italic>O<\/jats:italic>(\u0394<jats:sup><jats:italic>t<\/jats:italic><\/jats:sup>\/log \u0394) (as \u0394 \u2192 \u221e) for graphs of maximum degree at most \u0394 and girth at least 2<jats:italic>t<\/jats:italic>+1. The first bound is an analogue of Molloy and Reed's bound on the strong chromatic index. The second bound is tight up to a constant multiplicative factor, as certified by a class of graphs of girth at least <jats:italic>g<\/jats:italic>, for every fixed <jats:italic>g<\/jats:italic> \u2265 3, of arbitrarily large maximum degree \u0394, with distance-<jats:italic>t<\/jats:italic> chromatic index at least \u03a9(\u0394<jats:sup><jats:italic>t<\/jats:italic><\/jats:sup>\/log \u0394).<\/jats:p>","DOI":"10.1017\/s0963548313000473","type":"journal-article","created":{"date-parts":[[2013,11,14]],"date-time":"2013-11-14T13:47:14Z","timestamp":1384436834000},"page":"90-101","source":"Crossref","is-referenced-by-count":12,"title":["The Distance-<i>t<\/i> Chromatic Index of Graphs"],"prefix":"10.1017","volume":"23","author":[{"given":"TOM\u00c1\u0160","family":"KAISER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ROSS J.","family":"KANG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,11,14]]},"reference":[{"key":"S0963548313000473_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.001"},{"key":"S0963548313000473_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<357::AID-RSA9>3.0.CO;2-Y"},{"key":"S0963548313000473_ref6","unstructured":"Johansson A. (1996) Asymptotic choice number for triangle-free graphs. Technical report, DIMACS."},{"key":"S0963548313000473_ref2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1910"},{"key":"S0963548313000473_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(64)90028-6"},{"key":"S0963548313000473_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004965"},{"key":"S0963548313000473_ref9","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1724"},{"key":"S0963548313000473_ref3","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"S0963548313000473_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90163-5"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T01:10:57Z","timestamp":1555981857000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000473\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,14]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["S0963548313000473"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000473","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,14]]}}}