Computing Edge Chromatic Numbers of Graphs

Al Erickson, CECM, SFU

Wednesday January 24th, 2007 at 3:30pm in K9509.

Abstract: 

Computing the edge chromatic number of a simple graph is NP-Complete,
however, Vizing’s theorem states that there exists a ∆(G) + 1 edge
colouring. The proof is constructive and it offers us an algorithm
for finding such a colouring in polynomial time. 
We present an implementation of this and compare it to the tools
available in the GraphTheory package to be released in Maple 11.