Edge Colourings of Graphs

Michael Stiebitz

Technische Universitaet Ilmenau

Abstract

The chromatic index \chi'(G) of a (multi)graph G is the minimum number of colours needed to colour the edges of G such that adjacent edges receive distinct colours. The edge colouring problem is known to be NP-hard. For the chromatic index of G there are two natural lower bounds. On the one hand, \chi'(G) ≥ \Delta(G) where \Delta(G) is the maximum degree of $G$. On the other hand, \chi'(G)≥ \W(G) where

\W(G) =\max_{H\subseteq G}\left\lceil \frac{|E(H)|}{\lfloor \frac{1}{2}|V(H)|\rfloor} \right\rceil.

A graph G is called elementary if \chi'(G)=\W(G). Goldberg and, independently, Seymour conjectured in the 1970s that every graph G is elementary provided that \chi(G)> \Delta(G)+1. For an integer m≥ 3, let \J_m denote the class of all graphs G such that

\chi'(G)>\frac{m}{m-1}\Delta(G)+\frac{m-3}{m-1}.

Shannon's theorem implies that \J_3 is empty. Always \J_m\subseteq \J_{m+1} and the union of all \J_m with m≥3 consists of all graphs G such that \chi'(G)> \Delta(G)+1.

The conjecture has previously been proved for all graphs in \J_m for odd m up to 11. We use an extension of the method Tashkinov used for m=11 to prove that every graph in \J_{13} is elementary. The proof yields a polynomial-time algorithm to properly colour the edges of every graph G with at most \lfloor (13\chi'(G)+10)/12\rfloor colours.

Joint work with L. M. Favrholdt and B. Toft