13 - Graph colouring algorithms

Summary

This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available techniques and is organized by algorithmic paradigm.

Introduction

A straightforward algorithm for finding a vertex-colouring of a graph is to search systematically among all mappings from the set of vertices to the set of colours, a technique often called exhaustive or brute force:

Algorithm X (Exhaustive search) Given an integer q ≥ 1 and a graph G with vertexset V, this algorithm finds a vertex-colouring using q colours if one exists.

X1 [Main loop] For each mapping f : V → {1, 2, …, q}, do Step X2.

X2 [Check f] If every edge vw satisfies f(v) ≠ f(w), terminate with f as the result. ▪

This algorithm has few redeeming qualities, other than its being correct. We consider it here because it serves as an opportunity to make explicit the framework in which we present more interesting algorithms.

Model of computation

If G has n vertices and m edges, then the number of operations used by Algorithm X can be asymptotically bounded by O(qⁿ(n + m)), which we call the running time of the algorithm.

To make such a claim, we tacitly assume a computational model that includes primitive operations, such as iterating over all mappings from one finite set A to another finite set B in time O(|B|^|A|) (Step X1), or iterating over all edges in time O(n + m) (Step X2). For instance, we assume that the input graph is represented by an array of sequences indexed by vertices; the sequence stored at vertex v contains the neighouring vertices N(v), see Fig. 1. This representation allows us to iterate over the neighbours of a vertex in time O(deg v).