{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T19:05:06Z","timestamp":1775070306278,"version":"3.50.1"},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2018,3,25]],"date-time":"2018-03-25T00:00:00Z","timestamp":1521936000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:p>We consider distance colourings in graphs of maximum degree at most <jats:italic>d<\/jats:italic> and how excluding one fixed cycle of length \u2113 affects the number of colours required as <jats:italic>d<\/jats:italic> \u2192 \u221e. For vertex-colouring and <jats:italic>t<\/jats:italic> \u2a7e 1, if any two distinct vertices connected by a path of at most <jats:italic>t<\/jats:italic> edges are required to be coloured differently, then a reduction by a logarithmic (in <jats:italic>d<\/jats:italic>) factor against the trivial bound <jats:italic>O<\/jats:italic>(<jats:italic>d<jats:sup>t<\/jats:sup><\/jats:italic>) can be obtained by excluding an odd cycle length \u2113 \u2a7e 3<jats:italic>t<\/jats:italic> if <jats:italic>t<\/jats:italic> is odd or by excluding an even cycle length \u2113 \u2a7e 2<jats:italic>t<\/jats:italic> + 2. For edge-colouring and <jats:italic>t<\/jats:italic> \u2a7e 2, if any two distinct edges connected by a path of fewer than <jats:italic>t<\/jats:italic> edges are required to be coloured differently, then excluding an even cycle length \u2113 \u2a7e 2<jats:italic>t<\/jats:italic> is sufficient for a logarithmic factor reduction. For <jats:italic>t<\/jats:italic> \u2a7e 2, neither of the above statements are possible for other parity combinations of \u2113 and <jats:italic>t<\/jats:italic>. These results can be considered extensions of results due to Johansson (1996) and Mahdian (2000), and are related to open problems of Alon and Mohar (2002) and Kaiser and Kang (2014).<\/jats:p>","DOI":"10.1017\/s0963548318000068","type":"journal-article","created":{"date-parts":[[2018,3,25]],"date-time":"2018-03-25T18:02:19Z","timestamp":1522000939000},"page":"794-807","source":"Crossref","is-referenced-by-count":7,"title":["Distance Colouring Without One Cycle Length"],"prefix":"10.1017","volume":"27","author":[{"given":"ROSS J.","family":"KANG","sequence":"first","affiliation":[]},{"given":"FRAN\u00c7OIS","family":"PIROT","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,3,25]]},"reference":[{"key":"S0963548318000068_ref13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2012-11274-2"},{"key":"S0963548318000068_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<357::AID-RSA9>3.0.CO;2-Y"},{"key":"S0963548318000068_ref3","unstructured":"Bernshteyn A. (2017) The Johansson\u2013Molloy theorem for DP-coloring. arXiv:1708.03843"},{"key":"S0963548318000068_ref4","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s","year":"1978"},{"key":"S0963548318000068_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000473"},{"key":"S0963548318000068_ref12","unstructured":"Molloy M. (2017) The list chromatic number of graphs with small clique number. arXiv:1701.09133"},{"key":"S0963548318000068_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(64)90028-6"},{"key":"S0963548318000068_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90052-5"},{"key":"S0963548318000068_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/15M1035422"},{"key":"S0963548318000068_ref14","first-page":"117","article-title":"Some unsolved problems in graph theory.","volume":"23","author":"Vizing","year":"1968","journal-title":"Uspekhi Mat. Nauk"},{"key":"S0963548318000068_ref8","unstructured":"Johansson A. (1996) Asymptotic choice number for triangle-free graphs. Technical report 91-5, DIMACS."},{"key":"S0963548318000068_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004965"},{"key":"S0963548318000068_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70773-8"},{"key":"S0963548318000068_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1910"},{"key":"S0963548318000068_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004898"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T16:49:27Z","timestamp":1555174167000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000068\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,25]]},"references-count":15,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S0963548318000068"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000068","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,25]]}}}