CATERINA DE SIMONE
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:

Conjecture 1   Let be a graph with . Then if and only if contains no subgraph with and .

We shall prove this conjecture for some special case.