The distance-t chromatic index of graphs

Abstract

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-\eps)Δ^t$ for graphs of maximum degree at most $\Delta$, where $\eps$ is some absolute positive constant independent of $t$. The other is a bound of $O({\Delta }^t/\log \Delta )$ (as $\Delta \to \infty$) for graphs of maximum degree at most $\Delta$ 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\ge 3$, of arbitrarily large maximum degree $\Delta$, with distance-$t$ chromatic index at least $\Omega ({\Delta }^t/\log \Delta )$.

14 pages, 2 figures; to appear in Combinatorics, Probability and Computing

Cited by in corpus (2)

• Colouring powers and girth
• Distance colouring without one cycle length