
Computing Edge Chromatic Numbers of GraphsAl Erickson, CECM, SFU
Abstract: Computing the edge chromatic number of a simple graph is NPComplete, 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. 