Graph Colouring for Restricted Inputs

Background: A graph is a network of vertices (also called nodes) and links between vertices called edges that represent a relationship involving pairs of vertices. The Graph Colouring problem is that of labelling the vertices of a graph with the smallest possible number of integers (called colours) so that no two neighbouring vertices are identically coloured. Graph Colouring is an important concept in Mathematics and Computer Science due both to its many application areas crossing disciplinary boundaries and to its use as a benchmark problem in research into computational hardness. Well-known applications of Graph Colouring include map colouring, job or timetable scheduling, register allocation, colliding data or traffic streams, frequency assignment and pattern matching.

Research Aims: As the Graph Colouring problem is computationally hard in general, it is natural to restrict the input to special graph classes. By exploiting the graph structure we expect to find new efficient algorithms for special graph classes or else to obtain new intractability results. In this way we can identify the reasons for computational hardness, which will increase our understanding of how to deal with more general inputs; this bigger goal is our underlying general motivation. In particular we consider classes of pattern-free graphs, that is, those that are characterized by some forbidden pattern. The notion of being "pattern-free" captures a large number of well-studied graph classes, such as hereditary graph classes (for example, bipartite graphs, chordal graphs) and minor-closed graph classes (for example, planar graphs). The pattern depends upon the operations allowed when transforming one graph into another. Examples of such operations are vertex deletion, edge deletion, edge contraction and vertex dissolution. Important questions we will address are:

1.) Which pattern-free graphs allow efficient colouring algorithms?
Can we obtain full complexity classifications based on the pattern?
2.) Do dichotomies between computational hardness and efficiency even exist for certain
types of pattern? Why or why not?
3.) Can we extend obtained results to more general colouring problems such as precolouring
extension, list colouring, graph homomorphisms and on-line colouring?

Methodology: To answer the above questions we will apply the following approach:

1.) determine a useful structural property of the graph class under consideration (for
example, a small set of vertices adjacent to all other vertices of the graph);
2.) show that the critical subgraph (the part of the graph associated with the property) can
be detected e
ciently;
3.) colour the vertices of the critical subgraph in every possible way (using brute force);
4.) check if one of the partial colourings (\precolourings") can be extended to a colouring
of the whole graph by assigning each vertex in the uncoloured part a colour from a list
of colours forced upon the vertex by its precoloured neighbours.

To apply this outline 4-stage approach requires deep insight into specific graph structures (for steps 1-2) and the design of new colouring techniques to solve the precolouring extension and list colouring problems (for steps 3-4). We note that new approaches need to be developed as well. One reason for this is that the latter two problems may well be computationally hard for the speci fic graph class under consideration. We refer to the surveys [1,2] for details on both methodology for pattern-free graphs and a state-of-the-art description (full complexity classifications are still wide open for many pattern-free graph classes).