Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T18:31:37.771Z Has data issue: false hasContentIssue false
  • English
  • Français

The Distance-t Chromatic Index of Graphs

Published online by Cambridge University Press:  14 November 2013

TOMÁŠ KAISER  and
ROSS J. KANG
TOMÁŠ KAISER
Affiliation:
Department of Mathematics, Institute for Theoretical Computer Science (CE–ITI), and European Centre of Excellence NTIS (New Technologies for the Information Society), University of West Bohemia, Plzeň, Czech Republic (e-mail: kaisert@kma.zcu.cz)
ROSS J. KANG
Affiliation:
Mathematical Institute, Utrecht University, Utrecht, Netherlands (e-mail: ross.kang@gmail.com)
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 two graph colouring problems in which edges at distance at most t are given distinct colours, for some fixed positive integer t. We obtain two upper bounds for the distance-t chromatic index, the least number of colours necessary for such a colouring. One is a bound of (2-ε)Δt for graphs of maximum degree at most Δ, where ε is some absolute positive constant independent of t. The other is a bound of O(Δt/log Δ) (as Δ → ∞) for graphs of maximum degree at most Δ and girth at least 2t+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 g, for every fixed g ≥ 3, of arbitrarily large maximum degree Δ, with distance-t chromatic index at least Ω(Δt/log Δ).

Keywords

Primary 05C15Secondary 05C3505D4005C70

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 1 , January 2014 , pp. 90 - 101
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Alon, N. and Mohar, B. (2002) The chromatic number of graph powers. Combin. Probab. Comput. 11 1–10.Google Scholar
[2]Alon, N., Krivelevich, M. and Sudakov, B. (1999) Coloring graphs with sparse neighborhoods. J. Combin. Theory Ser. B 77 73–82.Google Scholar
[3]Erdős, P. (1959) Graph theory and probability. Canad. J. Math. 11 34–38.Google Scholar
[4]Faudree, R. J., Gyárfás, A., Schelp, R. H. and Tuza, Z. (1989) Induced matchings in bipartite graphs. Discrete Math. 78 83–87.CrossRefGoogle Scholar
[5]Feit, W. and Higman, G. (1964) The nonexistence of certain generalized polygons. J. Algebra 1 114–131.Google Scholar
[6]Johansson, A. (1996) Asymptotic choice number for triangle-free graphs. Technical report, DIMACS.Google Scholar
[7]Kang, R. J. and Manggala, P. (2012) Distance edge-colourings and matchings. Discrete Appl. Math. 160 2435–2439.Google Scholar
[8]Mahdian, M. (2000) The strong chromatic index of C 4-free graphs. Random Struct. Alg. 17 357–375.Google Scholar
[9]Molloy, M. and Reed, B. (1997) A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B 69 103–109.CrossRefGoogle Scholar