Graph Colouring with small monochromatic components





In Semester 1 2004, I did my final year computer science project on a very new and interesting topic.

In classical graph colouring, the aim is to assign a colouring to a graph such that no two edges have the same colour. Also, we want to reduce the number of colours that we use to an absolute minimum. This is a NP-Hard problem.

In graph colouring with small monochromatic components, we focus our attention to graphs of maximum degree 4. Furthermore, we only use two colours - black and white. The objective is to assign a colouring to the vertices which minimise the monochromatic components.

A monochromatic component is maximal connected monochromatic subgraph. That is, all vertices are of the same colour, and the subgraph is connected. Maximal here means that for all vertices adjacent to some vertex in the monochromatic component, none of these vertices are of the same colour as the colour of the subgraph. The concept of monochromatic component allows us to measure the performance of colour assigments.

Very little work has actually been conducted in this specific problem. My job was to implement two popular algorithms extracted from papers (references in my report). The proof from the first paper (which we implement as the EF algorithm) shows that the maximum monochromatic component size can be bounded sublinearly in terms of the number of vertices. The proof in the second paper (which we implement as the HST algorithm) shows that the maximum monochromatic component size can be bounded by a constant. However, in terms of the HST algorithm we require an NP-hard precondition to guarentee this. In my investigation, I devise extensions to the HST algorithm which seem to achieve this constant bound but in Polynomial time. This is the big conjecture I make in my work based on emperical evidence. Due to the lack of time, I was not able to attempt to prove this.

If you've read upto here, you probably want to read my report. My report is about 12000 words long. You probably don't want to read all of it because it also discusses the software. THe software, on the other hand is about 4200 lines of C code. Note that I have released the sources under GPL.  You can access then from the following links:


Latest Update (24/01/2005)

I have decided to convert this simple toolkit into an extensible tool for people interested in doing research, particularly with the 2 colour problem. Currently, I will keep the toolkit limited to the 2 colour problem, but I may possibly extend this toolkit in the near future. Furthermore, I will begin to write a Graphical tool which will be useful for analysis of output graphs from these algorithms. I will most likely make this for generalised graphs right from scratch (i.e., rather than concentrate on the 2 colour problem). One option for extensibility of this toolkit is to keep it very modular - so everything is done via a plugin system. This way, when we need to work with, say, the 2 colour problem, you can simply load the 2 colour plugin which will have the metrics etc neccessary to work with it.

So far, I have extended the toolkit in the following ways:
Currently, we're sitting on about 6000 lines of source, excluding header files.
Download latest source code for this software

Furthermore the following are the proposed extensions:


Back | Home