The functions given here are not applicable to digraphs.

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.

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.

Construct a largest clique in the graph G. The clique is returned as a set of vertices. (A clique is a subset of vertices which are all adjacent, so that the subgraph they generate is complete.)

Construct a clique of size n or greater in the graph G. The clique is returned as a set of vertices.

The size of a largest clique in the graph G.

The size of a largest independent set for the graph G. (An independent set is a subset of vertices no two of which are adjacent, so that the subgraph they generate is empty.)

Construct a largest independent set for the graph G as a set of vertices.

Construct an independent set for the graph G containing at least n vertices.

> G := Graph< 14 | [ { 2,11,7,6,9,8 }, { 13,11,3 }, { 10,4,14 }, { 14,10 }, { 7 },
>     { 7,11,12,9,8 }, { 11,9 }, { 1,9,6 }, { 11,12 }, { 11,14 },
>      { 1 }, { 1 }, { 2 }, { 3 } ]  >;
> ChromaticNumber(G);
5
> ChromaticIndex(G);
7
> // We look for a triangle in G, i.e. a clique of size 3
> Clique(G, 3);
{ 1, 2, 11 }
> LargestClique(G);
{ 1, 6, 7, 9, 11 }
> CliqueNumber(G);
5
> LargestIndependentSet(G);
{ 5, 8, 11, 12, 13, 14 }