CNR Rome

**Title:** Edge colouring

**Abstract:**
An *edge-colouring* of a graph is an assignment of colours to
its edges so that no two edges incident with the same vertex receive
the same colour; the minimum number of needed colours
is called the *chromatic index* of and is denoted by .

A celebrated theorem of Vizing (1964) states that, for a simple graph

where is the maximum degree of .

In 1985, Chetwynd and Hilton made the following conjecture:

We shall prove this conjecture for some special case.

Adrian Vetta 2003-11-07