A Greedy Method for Edge-Colouring Odd Maximum Degree Doubly Chordal Graphs

We describe a greedy vertex colouring method which can be used to colour optimally the edge set of certain chordal graphs. This new heuristic yields an exact edge-colouring algorithm for odd maximum degree doubly chordal graphs. This class includes interval graphs and strongly chordal graphs. This method shows that any such graph $G$ can be edge-coloured with maximum degree $\Delta(G)$ colours, i.e., all these graphs are Class $1$. In addition, this method gives a simple $\Delta(G) + 1$ edge-colouring for any doubly chordal graph.

1995