The Distance- t Chromatic Index of Graphs

Source 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-ε)Δ 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 2 t +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 Δ).