ALGB Seminar: Willem Haemers (Tilburg University)

Title: Coloring edges of strongly regular graphs

Abstract: 
The chromatic index (or edge-chromatic number) X'(G) of a graph G is the minimum number of colors needed to color the edges of G such that incident edges have different colours. Vizing proved that if k is the maximum degree of G, then X'(G)=k or k+1. If X'(G)=k, G is class 1, and if X'(G)=k+1, G is class 2. If G is class 1 and regular, then each color class is a perfect matching, and therefore a regular graph of odd order is class 2. For regular graphs of even order both classes occur. A regular graph is strongly regular if the number of common neighbours of any pair of vertices only depends on whether the vertices are adjacent or not. We determine the chromatic index of many strongly regular graphs and find enough support to conjecture that, except for the Petersen graph, every connected strongly regular graph of even order is class 1. This is joint work with Krystal Guo and Sebastian Cioaba