# 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

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010