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.