next up previous
Next: About this document ...

CATERINA DE SIMONE
CNR Rome


Title: Edge colouring


Abstract: An edge-colouring of a graph $G$ 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 $G$ and is denoted by $\chi'(G)$.

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


\begin{displaymath}\chi'(G)=\Delta(G)\quad \hbox{or} \quad \chi'(G)=\Delta(G)+1,\end{displaymath}

where $\Delta(G)$ is the maximum degree of $G$.

In 1985, Chetwynd and Hilton made the following conjecture:

Conjecture 1   Let $G$ be a graph with $\Delta(G)>\vert V(G)\vert/3$. Then $\chi'(G)=\Delta(G)$ if and only if $G$ contains no subgraph $H$ with $\Delta(H)=\Delta(G)$ and $\vert E(H)\vert > \Delta(H) \lfloor {{\vert V(H)\vert}\over2} \rfloor$.

We shall prove this conjecture for some special case.


Adrian Vetta 2003-11-07