Discrete Mathematics and Optimization Seminar


CATERINA DE SIMONE
CNR Rome
Monday October 27th at 4.30pm
Burnside 1205



Title. Edge Colouring.

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.