# Noon lecture

On 15.02.2007 at 12:20 in S5, there is the following noon lecture:

# Edge Colourings of Graphs

## 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) &#8805; \Delta(G) where \Delta(G) is the maximum degree of $G$. On the other hand, \chi'(G)&#8805; \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&#8805; 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&#8805;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

Modified: 19. 10. 2010