---
title: "Colourings"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/colouring.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/colouring.md"
part: "Combinatorics"
chapter: "Graphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "Directed Trees", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/directed-tree.md"}
next: {"title": "Cliques, Independent Sets", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/clique-independent-set.md"}
intrinsics:
  - {"name": "ChromaticNumber", "signature": "ChromaticNumber(G): GrphUnd -> RngIntElt"}
  - {"name": "OptimalVertexColouring", "signature": "OptimalVertexColouring(G): GrphUnd -> SeqEnum"}
  - {"name": "ChromaticIndex", "signature": "ChromaticIndex(G): GrphUnd -> RngIntElt"}
  - {"name": "OptimalEdgeColouring", "signature": "OptimalEdgeColouring(G): GrphUnd -> SeqEnum"}
  - {"name": "ChromaticPolynomial", "signature": "ChromaticPolynomial(G): GrphUnd -> RngUPolElt"}
examples:
  - "ex-8c2867"
---

<a id="colouring"></a>
<a id="graph-sec-colour"></a>
# Colourings

The functions given here are not applicable to digraphs.

<a id="function-chromaticnumber-grphund"></a>
## `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.

<a id="function-optimalvertexcolouring-grphund"></a>
## `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.

<a id="function-chromaticindex-grphund"></a>
## `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.

<a id="function-optimaledgecolouring-grphund"></a>
## `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.

<a id="function-chromaticpolynomial-grphund"></a>
## `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$.

<a id="example-ex-8c2867"></a>
## `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
```
