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 pG(x) gives the number of colourings of G with colours 1, 2, ..., x.

Example Graph_ChromaticNumber (H158E15)

We illustrate the use of these functions with the following graph: 
> 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
V2.28, 13 July 2023