The distance-t chromatic index of graphs.

Tomàš Kaiser, Ross Kang

Research output: Contribution to journalArticleAcademicpeer-review

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 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 Δ).
Original languageEnglish
Pages (from-to)90-101
Number of pages12
JournalCombinatorics, Probability and Computing
Volume23
Issue number1
Early online date14 Nov 2013
DOIs
Publication statusPublished - Jan 2014

Fingerprint

Dive into the research topics of 'The distance-t chromatic index of graphs.'. Together they form a unique fingerprint.

Cite this