# Colourings

The functions given here are not applicable to digraphs.

## `ChromaticNumber(G): GrphUnd -> RngIntElt`

The chromatic number of the graph $G$, that is, the minimum number of colours required to colour the vertices of $G$ such that no two adjacent vertices share the same colour.

## `OptimalVertexColouring(G): GrphUnd -> SeqEnum`

An optimal vertex colouring of the graph $G$ as a sequence of sets of vertices of $G$. Each set in the sequence contains the vertices which are given the same colour. Some optimal vertex colouring is returned, others may exist.

## `ChromaticIndex(G): GrphUnd -> RngIntElt`

The chromatic index of the graph $G$, that is, the minimum number of colours required to colour the edges of $G$ such that no two adjacent edges share the same colour.

## `OptimalEdgeColouring(G): GrphUnd -> SeqEnum`

An optimal edge colouring of the graph $G$ as a sequence of sets of edges of $G$. Each set in the sequence contains the edges which are given the same colour. Some optimal edge colouring is returned, others may exist.

## `ChromaticPolynomial(G): GrphUnd -> RngUPolElt`

The chromatic polynomial of the graph $G$. For a given natural number $x$, the chromatic polynomial $p_{G}(x)$ gives the number of colourings of $G$ with colours $1, 2, \ldots, x$.

## `Example: Chromatic Number (ex-8c2867)`

We illustrate the use of these functions with the following graph:

```magma
> G:=Graph< 5 | [{2,5}, {1,3,5}, {2,4,5}, {3,5}, {1,2,3,4} ]>;
> ChromaticNumber(G);
3
> OptimalVertexColouring(G);
[
  { 1, 3 },
  { 2, 4 },
  { 5 }
]
> ChromaticIndex(G);
4
> OptimalEdgeColouring(G);
[
  { {1, 2}, {3, 5} },
  { {2, 3}, {1, 5} },
  { {3, 4}, {2, 5} },
  { {4, 5} }
]
> ChromaticPolynomial(G);
$.1^5 - 7*$.1^4 + 18*$.1^3 - 20*$.1^2 + 8*$.1

```