Chapter 6. Colouring

Graph colouring is one of the fundamental topics in graph theory. It consists of assigning colours to certain elements of a graph (its vertices or its edges) subject to specific constraints. The main objective is to perform this colouring using the smallest possible number of colours while ensuring that adjacent elements do not share the same colour.
This chapter presents the essential concepts and results related to graph colouring.
In the first section, we introduce the basic definitions of vertex and edge colouring and the associated notions such as chromatic number and chromatic index.
The second section focuses on vertex colouring, which consists of partitioning the set of vertices into stable subsets.
The third section deals with arc (edge) colouring, where colours are assigned to the edges of the graph so that adjacent edges receive different colours.
The fourth section recalls some important propositions and theorems, including bounds on the chromatic number.
The fifth section presents the famous Four Colour Theorem, which applies to planar graphs and states that any planar map can be coloured with at most four colours.
Finally, the sixth section introduces the notion of perfect graphs, an important class of graphs in which the chromatic number equals the size of the largest clique for every induced subgraph.