Documentation

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

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.

Syntax

Graph::chromaticPolynomial(G, x)

Description

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.

Examples

Example 1

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:

Example 2

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)

Parameters

G

An undirected graph

x

An identifier

Return Values

polynomial

References

See Birkhoff and Lewis, Chromatic Polynomials, Trans. AMS, Vol. 60, p.355–451, 1946.

Algorithms

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 2n.

Was this topic helpful?