Mathematica 9 is now available

Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title Downloads

Fast Edge Colouring of Graphs
Author

Ágnes Tóth
Organization: Budapest University of Technology and Economics
Conference

2007 Wolfram Technology Conference
Conference location

Champaign, IL
Description

Abstract

An edge colouring of a graph is assumed to be a proper colouring of the edges, meaning that no two edges, sharing a common vertex, are assigned the same color. The edge chromatic number gives the minimum number of colors with which a graph can be colored. Finding the minimum edge colouring of a graph is equivalent to finding the minimum vertex colouring of its line graph. So edge colouring is a special case of vertex colouring. Moreover, edge colouring of graphs is an easier problem than colouring of graphs generally. By Vizing's theorem, the edge chromatic number of a simple graph can take only two values, Δ or Δ+1 (where Δ means the maximum degree of a graph). And Vizing's proof by Misra and Gries also implies an algorithm that colors the edges of a graph with at most Δ+1 colors in polynomial time, whereas the vertex colouring problem is NP-complete.

An edge colouring of a graph can be computed using the function EdgeColoring in the Mathematica add-on package Combinatorica Package. This function constructs the line graph of the graph, and colours its vertices using Brelaz's heuristic. So this method cannot be as fast and it may use more than Δ+1 colours in some cases.

That is the reason why I have implemented Misra and Gries's algorithm in Mathematica. In my document I test this function and compare it with Mathematica's EdgeColoring. The result confirms the theory, the algorithm uses at most Δ+1 colors. And surprisingly, it is also faster than Mathematica's method. I have also tested the method on random graphs and on various graph families.

I have also used an animation to demonstrate how the algorithm colors the edges: in which order get the edge color and if it is needed which edges are recolored.

After this success I tried to improve vertex colouring with Mathematica, too. I have implemented Klotz's contraction algorithm, which uses fewer colors, but needs more running time than the function Mathematica's VertexColoring. I have also implemented another algorithm of Finocchi, Panconesi, and Silvestri that also can be parallelized.
Subject

*Mathematica Technology
URL

http://www.wolfram.com/news/events/techconf2007/
Downloads

Download
FastEdgeColouring.zip (1.1 MB) - ZIP archive [for Mathematica 6.0]