The distance-t chromatic index of graphs

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 num-ber 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 posi-tive 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 ∆)