Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T18:01:32.322Z Has data issue: false hasContentIssue false
  • English
  • Français

Distance Colouring Without One Cycle Length

Published online by Cambridge University Press:  25 March 2018

ROSS J. KANG  and
FRANÇOIS PIROT
ROSS J. KANG
Affiliation:
Department of Mathematics, Radboud University Nijmegen, PO Box 9010, 6500 GL Nijmegen, Netherlands (e-mail: [email protected])
FRANÇOIS PIROT
Affiliation:
LORIA, Campus Scientifique, 615 Rue du Jardin-Botanique, 54506 Vandœuvre-lès-Nancy, France (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider distance colourings in graphs of maximum degree at most d and how excluding one fixed cycle of length ℓ affects the number of colours required as d → ∞. For vertex-colouring and t ⩾ 1, if any two distinct vertices connected by a path of at most t edges are required to be coloured differently, then a reduction by a logarithmic (in d) factor against the trivial bound O(dt) can be obtained by excluding an odd cycle length ℓ ⩾ 3t if t is odd or by excluding an even cycle length ℓ ⩾ 2t + 2. For edge-colouring and t ⩾ 2, if any two distinct edges connected by a path of fewer than t edges are required to be coloured differently, then excluding an even cycle length ℓ ⩾ 2t is sufficient for a logarithmic factor reduction. For t ⩾ 2, neither of the above statements are possible for other parity combinations of ℓ and t. 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).

Keywords

Primary 05C15Secondary 05C3505C70
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 5 , September 2018 , pp. 794 - 807
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © Cambridge University Press 2018

Footnotes

†

Supported by a Vidi (639.032.614) grant of the Netherlands Organisation for Scientific Research (NWO).

References

[1] Alon, N., Krivelevich, M. and Sudakov, B. (1999) Coloring graphs with sparse neighborhoods. J. Combin. Theory Ser. B 77 73–82.Google Scholar
[2] Alon, N. and Mohar, B. (2002) The chromatic number of graph powers. Combin. Probab. Comput. 11 1–10.Google Scholar
[3] Bernshteyn, A. (2017) The Johansson–Molloy theorem for DP-coloring. arXiv:1708.03843Google Scholar
[4] Bollobás, B. (1978) Extremal Graph Theory, Vol. 11 of London Mathematical Society Monographs, Academic Press.Google Scholar
[5] Bondy, J. A. and Simonovits, M. (1974) Cycles of even length in graphs. J. Combin. Theory Ser. B 16 97–105.Google Scholar
[6] Erdős, P. (1988) Problems and results in combinatorial analysis and graph theory. Ann. Discrete Math. 38 81–92.Google Scholar
[7] Feit, W. and Higman, G. (1964) The nonexistence of certain generalized polygons. J. Algebra 1 114–131.Google Scholar
[8] Johansson, A. (1996) Asymptotic choice number for triangle-free graphs. Technical report 91-5, DIMACS.Google Scholar
[9] Kaiser, T. and Kang, R. J. (2014) The distance-t chromatic index of graphs. Combin. Probab. Comput. 23 90–101.Google Scholar
[10] Kang, R. J. and Pirot, F. (2016) Coloring powers and girth. SIAM J. Discrete Math. 30 1938–1949.Google Scholar
[11] Mahdian, M. (2000) The strong chromatic index of C 4-free graphs. Random Struct. Alg. 17 357–375.Google Scholar
[12] Molloy, M. (2017) The list chromatic number of graphs with small clique number. arXiv:1701.09133Google Scholar
[13] Pikhurko, O. (2012) A note on the Turán function of even cycles. Proc. Amer. Math. Soc. 140 3687–3692.Google Scholar
[14] Vizing, V. G. (1968) Some unsolved problems in graph theory. Uspekhi Mat. Nauk 23 117–134.Google Scholar
[15] Vu, V. H. (2002) A general upper bound on the list chromatic number of locally sparse graphs. Combin. Probab. Comput. 11 103–111.Google Scholar