# Greedy Edge Colouring of Small Graphs

26 Sep 2014In seveal earlier posts we looked at greedy vertex-colouring of small graphs. As we saw, a greedy approach to vertex-colouring is quite successful in so far as it uses at most colours to colour any graph .

It is easy to modify the greedy method to colour the edges of a graph. However, we cannot guarantee that the number of colours used will be as few as . The best that we can guarantee with the simplest greedy approach to edge-colouring is no more than colours.

It’s not difficult to see why this is, for suppose that we have coloured some edges of the graph and come to colour edge . There might be as many as colours on edges incident with and the same amount on edges incident with . In the worst case, all of these colours might be different and so we need at least colours in our palette to be certain, without recolouring, to have a colour available for edge .

In this post we introduce a NetworkX-based implementation of greedy
edge-colouring for graphs in *graph6* format. Using this implementation we
investigate the average case performance on all non-isomorphic, connected simple
graphs of at most nine vertices. It turns out that, on average, the greedy
edge-colouring method uses many fewer colours than the worst case of
.

As we will discuss, the theory of edge-colouring suggests that with large sets of simple graphs we can get close, on average, to the best case of colours.

## Greedy Edge-Colouring with NetworkX

The core of our implementation is a function that visits every edge of a graph and assigns a colour to each edge according to a parametrised colour choice strategy.

```
def edge_colouring(G, choice = choice_greedy):
max_degree = max(G.degree().values())
palette = range(0, 2*max_degree)
for e in G.edges():
colour_edge(G, e, choice(G, e, palette))
```

This function allows for some flexibility in the method used to choose the colour assigned to a certain edge. Of course, it lacks flexibility in certain other respects. For example, both the order in which edges are visited and the palette of colours are fixed.

Everything in the implementation is either Python or NetworkX, except for the
`colour_edge(G, e, c)`

and `choice(G, e, p)`

functions. The former simply
applies colour `c`

to edge `e`

in graph `G`

. The latter, a function parameter
that can be specified to implement different colouring strategies, decides the
colour to be used.

For greedy colouring the choice strategy is plain enough. For edge
in graph we choose the first colour from a palette of colours which is
not used on edges incident with either vertex or vertex . The
implementation, below, is made especially simple by Python’s `Set`

s.

```
def choice_greedy(G, e, palette):
used_colours = used_at(G, e[0]).union(used_at(G, e[1]))
available_colours = set(palette).difference(used_colours)
return available_colours.pop()
```

Here `used_at(G, u)`

is a function that returns a `Set`

of all colours used on
edges incident with `u`

in `G`

. So, via the `union`

operation on `Sets`

,
`used_colours`

becomes the set of colours used on edges incident with
end-vertices of `e`

. The returned colours is then the colour on the top of
`available_colours`

, the set difference of `palette`

and `used_colours`

.

## Edge-Colouring Small Graphs

The implementation described in the previous section has been put into a script
that processes graphs in *graph6* format and returns, not the edge-colouring,
but the number of colours used. For example, the number of colours used in a
greedy edge-colouring of the Petersen graph is four:

```
$ echo ICOf@pSb? | edge_colouring.py
4
```

As in earlier posts on vertex-colouring we now consider the set of all non-isomorphic, connected, simple graphs and study the average case performance of our colouring method on this set. For vertex-colouring, parallel edges have no effect on the chromatic number and thus the set of simple graphs is the right set of graphs to consider. For edge-colouring we ought to look at parallel edges and thus the set of multigraphs because parallel edges can effect the chromatic index. We will save this case for a future post.

Also in common with earlier posts, here we will use *Drake* as the basis for our
simulation. The hope being that others can reproduce our results by downloading
our `Drakefile`

and running it.

We continue to use *geng* from *nauty* to generate the graph data we are
studying. For example, to colour all non-isomorphic, connected, simple graphs on
three vertices and count the colour used:

```
$ geng -qc 3 | edge_colouring.py
2
3
```

So, of the two graphs in question, one () has been coloured with two colours and the other () has been coloured with three colours.

As with vertex-colouring, the minimum number of colours in a proper edge-colouring of a graph is . In contrast, though, by Vizing’s theorem, at most one extra colour is required.

**Theorem (Vizing)**

A graph for which is called *Class One*.
If then is called *Class Two*. By Vizing’s
theorem every graph is Class One or Class Two. is an example of a
graph that is Class One and is an example of a Class Two graph.

Vizing’s theorem says nothing, however, about how many colours our greedy colouring program will use. We might, though, consider it moderately successful were it to use not many more than colours on average.

So we are going to consider the total number of colours used to colour all graphs of order as a proportion of the total maximum degree over the same set of graphs.

To compute total number of colours used we follow this tip on summing values in
the console using *paste* and *bc*:

```
$ geng -qc 3
| edge_colouring.py
| paste -s -d+
| bc
5
```

To compute maximum degrees we depend upon the *maxdeg* program for *gvpr*. This
means that we have to pipe the output of *geng* through *listg* to convert it
into *DOT* format:

```
$ geng -qc 3
| listg -y
| gvpr -fmaxdeg
max degree = 2, node 2, min degree = 1, node 0
max degree = 2, node 0, min degree = 2, node 0
```

The output from *maxdeg* contains much more information than we need and so we
need to pipe the output through *sed* to strip out the maximum degrees:

```
$ geng -qc 3
| listg -y
| gvpr -fmaxdeg
| sed -n 's/max degree = \([0-9]*\).*/\1/p'
2
2
```

Now, piping through *paste* and *bc* as before, we find the total over all
graphs of the maximum degrees:

```
$ geng -qc 3
| listg -y
| gvpr -fmaxdeg
| sed -n 's/max degree = \([0-9]*\).*/\1/p'
| paste -s -d+
| bc
4
```

Perhaps surprisingly, with this approach, we find a relatively small discrepancy between the total number of colours used and the total maximum degree. For example, for (below) the discrepancy is 18 or 25%.

```
$ time geng -qc 5
| edge_colouring.py
| paste -s -d+
| bc
90
real 0m0.416s
user 0m0.328s
sys 0m0.068s
```

```
$ time geng -qc 5
| listg -y
| gvpr -fmaxdeg
| sed -n 's/max degree = \([0-9]*\).*/\1/p'
| paste -s -d+
| bc
72
real 0m0.014s
user 0m0.004s
sys 0m0.004s
```

For the discrepancy is 9189586, or less than 12% of the total of maximum degrees.

```
$ time geng -qc 10
| edge_colouring.py
| paste -s -d+
| bc
87423743
real 135m6.838s
user 131m38.614s
sys 0m12.305s
```

```
$ time geng -qc 10
| listg -y
| gvpr -fmaxdeg
| sed -n 's/max degree = \([0-9]*\).*/\1/p'
| paste -s -d+
| bc
78234157
real 48m52.294s
user 51m43.042s
sys 0m12.737s
```

## Results

We repeated the experiment described in the previous section for all values of from 2 to 10. The results are presented in the plot below which is based on Matplotlib basic plotting from a text file.

For all orders the total number of colours used by our greedy method is between 1 and 1.5 times the total maximum degree. There also seems to be a tendancy towards a smaller proportion for larger values of . Two theoretical results are relevant here.

The first is Shannon’s theorem which concerns the chromatic index of multigraphs:

**Theorem (Shannon)**

Shannon’s theorem applies for our experiment because every simple graph is a multigraph with maximum multiplicity 1. An interesting experiment is to see if the results of the above experiment extend to multigraphs. Shannon’s theorem guarantees that for some colouring method it is possible but says nothing about the performance of our specific method.

A result which is relevant to the second observation, that the proportion tends to 1, concerns the distribution of simple graphs among Class One and Class Two.

**Theorem (10.5 from (Chartrand & Zhang, 2008))**

Almost every graph is Class One, that is

where denotes the set of graphs of order and is the set of Class One graphs of order .

So we have good reason to hope that, on average, with larger sets of simple graphs we use fewer colours on average.

In the source code section below there is a *Drakefile* which should reproduce
this plot from scratch (provided that the required software is installed).