Colouring Small Graphs

In Chromatic Polynomials we showed how to partially reproduce the data on small graph colourings made available by Gordon Royle. In that post we used NetworkX, sympy and the tutte_bhkk module of Björklund et al. (2008) to reproduce Royle’s results up to order \(n = 7\).

In A Chromatic Number Program we developed a tool, chromatic, for computing chromatic numbers based on tutte, an implementation of the Tutte polynomial by Haggard, Pearce, and Royle (2010) .

In this post we attempt to reproduce Royle’s chromatic number distribution data with chromatic.

A Small Chromatic Hack

The chromatic script that we introduced last week had at least one flaw. It was not able to correctly calculate the chromatic number of a graph with no edges. This seems to be due to the fact that the input format for the tutte program used to calculate the chromatic polynomial does not support empty (i.e. edge-less) graphs.

One solution, shown below, is to calculate, using the Graphviz program gc the number of edges in the input graph. If this number is zero then we return 1 and exit the script.

n_edges=`gc -e $file_gv\
         | sed -n 's/\([0-9]*\) %.*/\1/p'\
         | tr -d ' '`

if [[ ${n_edges} -eq 0 ]] ; then
    echo 1
    exit 1
fi

Simulation Overview

Most of the work in this simulation is done by a single Bash script. In addition to looping through the graph data computing chromatic numbers we also have to first convert data into the right format and, afterwards, analyse the results.

More specifically, we have to do the following things:

1. Convert graph6 graph data from Brendan McKay’s homepage into Graphviz DOT format.
2. Iterate through all connected graphs of order at most 7 and for each graph compute the chromatic number and append it to a file of chromatic numbers of all connected graphs of the same order.
3. Analyse the distribution of chromatic numbers in the resulting results files.

In the rest of this post we describe each of these steps in more detail.

Data Conversion

We begin with the small graph data from Brendan McKay’s homepage. Among the various files he has made available are a collection which contain all graphs of order 10 or less. These are made available in graph6 format with one graph per line in files that contain all graphs of a specific order. A separate collection gives all of the connected graphs of order at most 10. The latter is the collection we are going to be using.

As things stand, chromatic, reads one graph at a time from an input file and that graph is expected to be in Graphviz DOT format. In the future it will be possible to run chromatic directly on graph6 data but for now we just do the conversion to DOT format before running the simulation.

A Makefile that converts the graph6 data into folders of files in DOT format, with one file per graph, has been added to the graphs-collection project. So to build this data we now merely clone the graphs-collection repository and call make from the src/Small folder.

Doing this creates a new folder src/Small/output which contains subfolders n_gv and nc_gv for all \(2 \leq n \leq 8\). The folder n_gv contains all graphs of order \(n\) in DOT format and the folder nc_gv contains all connected graphs of order \(n\) in DOT format.

The Main Loop

Once we have the data in DOT format our simulation is a very simple Bash script that takes two arguments, a lower and upper bound. The chromatic numbers of all (connected) graphs of orders between the lower and upper bounds are computed and stored in results files, one chromatic number per line, for subsequent analysis.

#!/bin/bash

BASEDIR=~/workspace/graphs-collection/src/Small/output

for order in `seq $1 $2`;
do
 echo ${order}
 graphs=`ls `\({BASEDIR}/\)`{order}c_gv/*`
 for graph in ${graphs};
 do
  chromatic ${graph} >> ${order}c_result.txt;
 done
done

The BASEDIR variable in this script points to the output folder generated in the previous step.

Analysis

A second small Bash script now is used to process the output from the previous step and collate the chromatic numbers for each order. This script also takes two parameters as input, the upper and lower bounds on order.

#!/bin/bash

RESULTS_DIR=results/14_07_31_results

for i in `seq $1 $2`
do
 echo order: $i
 for j in `seq 1 8`
 do
 echo $j: `grep -c $j `\({RESULTS_DIR}/\)`{i}c_result.txt`
 done
done

Here RESULT_DIR points to the location of the folder containing the output from the previous step

Results

The data collected by the simulation described above agrees with Royle’s table for all \(n \leq 6\). For \(n = 7\) we get the following numbers, which are obviously wrong.

We would expect that the number of connected graphs of order 7 having chromatic number 7 is (at least) 1. We also expect that there are connected graphs of order 7 having chromatic number 6. Those last two zeros, therefore, point to a flaw in our simulation.

It seems most likely that the error was introduced in converting the data from graph6 to DOT format. Our methods for converting are not designed with much rigour and it seems plausible that they aren’t reliable for larger graphs. There are at least a couple of things we can do to progress and hopefully fix this problem.

One method is to improve the reliability of our conversion tools. To do this we should match the conversions described in the Makefile in graphs-collection with some testing of basic parameters in the resulting data.

Another approach is to modify chromatic to work with files in graph6 one graph per line format.

In upcoming posts we will look at both of these approaches and return to Royle’s data with a view to reproducing his results as far as possible.

References