|
|
|
|
|
|
 |
 |
|
Fast Edge Colouring of Graphs
|
|
|
|
|
|
| Organization: | Budapest University of Technology and Economics |
|
|
|
|
|
|
2007 Wolfram Technology Conference
|
|
|
|
|
|
Champaign, IL
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
http://www.wolfram.com/news/events/techconf2007/
|
|
|
|
|
|
| FastEdgeColouring.zip (1.1 MB) - ZIP archive [for Mathematica 6.0] |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
