|
The functions given here are not applicable to digraphs.
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.
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.
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.
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.
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.
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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|