2002 | OriginalPaper | Chapter
Colouring Preliminaries
Authors : Michael Molloy, Bruce Reed
Published in: Graph Colouring and the Probabilistic Method
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We will be discussing colouring the vertices and edges of graphs. A graph G is a set V = V (G) of vertices and a set E = E(G) of edges,each linking a pair of vertices, its endpoints (formally, an edge is an unordered pair of vertices and thus our graphs have no loops or multiple edges), which are adjacent. We assume the reader has a basic knowledge of graph theory. A k-colouring of the vertices of a graph G is an assignment of k colours (often the integers 1,..., k) to the vertices of G so that no two adjacent vertices get the same colour. The chromatic number of G, denoted χ(G), is the minimum k for which there is a k-colouring of the vertices of G. The set S j of vertices receiving colour j is a colour class and induces a graph with no edges, i.e. it is a stable set or independent set. So, a k-colouring of the vertices of G is simply a partition of V(G) into k stable sets and the chromatic number of G is the minimum number of stable sets into which the vertices of G can be partitioned.