Accelerating the pace of engineering and science

# Documentation Center

• Trial Software
• Product Updates

# Graph::chromaticPolynomial

Calculates a chromatic polynomial

### Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

## 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

polynomial

## 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.

## References

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

Was this topic helpful?