Graph
::chromaticPolynomial
Calculates a chromatic polynomial
MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.
MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.
Graph::chromaticPolynomial(G
, x
)
Graph::chromaticPolynomial(G, x)
returns
the chromatic polynomial of the graph G
. Evaluating
the result at x = n,
for any integer n,
gives the number of possible ways to color the graph G
using n colors
such that no two adjacent vertices have the same color.
G
must be an undirected graph: if an edge
goes from a tob,
another edge must go from b to a,
for any two verticesa, b.
We compute the chromatic polynomial of the complete graph with 5 vertices:
f:= Graph::chromaticPolynomial(Graph::createCompleteGraph(5), x)
There are 240 ways to color a complete graph with 5 vertices, since this is the number of bijective mappings between the set of colors and the set of vertices:
f(5)
delete f:
Now let us delete one edge from a complete graph:
G:= Graph::createCompleteGraph(5): G:= Graph::removeEdge(G, [[2, 3]]): G:= Graph::removeEdge(G, [[3, 2]])
Now there are some additional possible colourings: vertices 2 and 3 may now have the same color, in five different ways; in each case, there must be one of the four remaining colors that does not occur at all. In each of the 20 cases, we are left with 3 vertices that form a complete graph and 3 colors, such that there are 6 colourings. Altogether this gives us 120 additional colourings:
Graph::chromaticPolynomial(G, x)(5)

An undirected graph 

An identifier 
See Birkhoff and Lewis, Chromatic Polynomials, Trans. AMS, Vol. 60, p.355–451, 1946.
Computing the chromatic polynomial of a graph with n vertices reduces to computing two chromatic polynomials of graphs with n  1 vertices. The running time is hence roughly 2^{n}.