### Graph colouring with small monochromatic components

#### Graham Farr

In classical graph colouring, every vertex of a graph
is to be given a colour in such a way that adjacent vertices
receive different colours. The aim is to do this with as
few colours as possible. Such problems have a long and
fascinating history going back over 150 years, and have
many applications, e.g. exam timetabling, register
allocation. Most problems of this kind are NP-hard,
which suggests they are very difficult to solve exactly,
so there is a need for algorithms that run quickly and
find a reasonable (but usually not optimum) colouring.

This project concerns a recent extension to this problem,
where we relax somewhat the abovementioned ban on adjacent
vertices receiving the same colour.
Suppose we allow adjacent vertices to be coloured the same,
but we still don't want too many identically-coloured vertices
to be linked up together in a connected subgraph.
Let's make this more precise.

Let *G* be any graph. Suppose we use *k* colours.
Look at the largest connected subgraph of *G* in which
all vertices of the subgraph receive the same colour.
Suppose this subgraph has *C* vertices.
We say that *G* is [*k*,*C*]-colourable
if it can be coloured with at most *k* colours in this way,
with the largest connected monochromatic subgraph having
at most *C* vertices.

The aim of the project is to implement and study some algorithms
that find such colourings, while trying to keep *k*
or *C* small. We will focus on graphs with
maximum degree 4,
and on trying to minimise *C* while using just two colours.
Algorithms to be considered are based on reasonably simple ideas
and will include
one due to
Keith Edwards (Dundee) and myself,
another from the literature, and one you design yourself.
Work to be done includes implementing these algorithms,
studying their performance (in minimising *C*) and running
time on graphs
of various sizes including randomly generated graphs, drawing
conclusions from the experimental results obtained, and writing
up the final report.

Programming will be in C. There are no prerequisites beyond
the standard core Computer Science curriculum; the most valuable
subject to have is probably cse2304 Algorithms and Data Structures.
So if you hated that, then this project may not be the best one for you.

First meeting: Wed 10 March 1-2pm, rm 111, 1st floor, bldg 75.
At this meeting we can attempt to arrange a better time for
everyone, if that can be found. If not, we will default to
every Wed at above time and place.