WOLFRAM

Wolfram Language & System Documentation Center

ChromaticPolynomial[g,k]

gives the chromatic polynomial of the graph g.

ChromaticPolynomial[{vw,…},…]

uses rules vw to specify the graph g.

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

ChromaticPolynomial

ChromaticPolynomial[g,k]

gives the chromatic polynomial of the graph g.

ChromaticPolynomial[{vw,…},…]

uses rules vw to specify the graph g.

Details

Examples

open all close all

Basic Examples  (1)

The chromatic polynomial of a cycle graph:

Wolfram Language code: ChromaticPolynomial[CycleGraph[3], k]

Plot the polynomial:

Wolfram Language code: DiscretePlot[%, {k, 20}]

Scope  (6)

ChromaticPolynomial works with undirected graphs:

Wolfram Language code: ChromaticPolynomial[[image], k]

Directed graphs:

Wolfram Language code: ChromaticPolynomial[[image], k]

Multigraphs:

Wolfram Language code: ChromaticPolynomial[[image], k]

Mixed graphs:

Wolfram Language code: ChromaticPolynomial[[image], k]

Use rules to specify the graph:

Wolfram Language code: ChromaticPolynomial[{1 -> 3, 2 -> 1, 3 -> 6, 4 -> 6, 1 -> 5, 5 -> 4, 6 -> 1}, k]

Evaluate at specific value:

Wolfram Language code: ChromaticPolynomial[[image], 3]

Applications  (3)

Compute the number of 3-colorings of the Petersen graph:

Wolfram Language code: ChromaticPolynomial[PetersenGraph[], 3]

Find the chromatic number of a graph:

Wolfram Language code: p[k] = ChromaticPolynomial[PetersenGraph[], k]
Wolfram Language code: MinValue[{k, k > 0 && p[k] > 0 }, k, Integers]

Chromatic polynomials for complete graphs with vertices:

Wolfram Language code: Table[ChromaticPolynomial[CompleteGraph[n], k], {n, 1, 7}]
Wolfram Language code: FindSequenceFunction[%, n]

Cycle graphs:

Wolfram Language code: Table[ChromaticPolynomial[CycleGraph[n], k], {n, 1, 7}]
Wolfram Language code: FindSequenceFunction[%, n]

Properties & Relations  (3)

Use TuttePolynomial to compute ChromaticPolynomial:

Wolfram Language code: g = WheelGraph[5];
Wolfram Language code: {n, c} = {VertexCount[g], Length[ConnectedComponents[g]]};
Wolfram Language code: (-1)^n - ck^c * TuttePolynomial[g, {1 - k, 0}]//Expand
Wolfram Language code: ChromaticPolynomial[g, k]

A graph with vertices is a tree if and only if its chromatic polynomial is k(k-1)n-1:

Wolfram Language code: g = KaryTree[3];
Wolfram Language code: TreeGraphQ[g]
Wolfram Language code: {ChromaticPolynomial[g, k], k(k - 1)^VertexCount[g] - 1}//Expand

Isomorphic graphs have the same chromatic polynomial:

Wolfram Language code: g = [image];h = [image];
Wolfram Language code: IsomorphicGraphQ[g, h]
Wolfram Language code: ChromaticPolynomial[g, k] == ChromaticPolynomial[h, k]
Wolfram Research (2014), ChromaticPolynomial, Wolfram Language function, https://reference.wolfram.com/language/ref/ChromaticPolynomial.html (updated 2015).

Text

Wolfram Research (2014), ChromaticPolynomial, Wolfram Language function, https://reference.wolfram.com/language/ref/ChromaticPolynomial.html (updated 2015).

CMS

Wolfram Language. 2014. "ChromaticPolynomial." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/ChromaticPolynomial.html.

APA

Wolfram Language. (2014). ChromaticPolynomial. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/ChromaticPolynomial.html

BibTeX

@misc{reference.wolfram_2026_chromaticpolynomial, author="Wolfram Research", title="{ChromaticPolynomial}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/ChromaticPolynomial.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_chromaticpolynomial, organization={Wolfram Research}, title={ChromaticPolynomial}, year={2015}, url={https://reference.wolfram.com/language/ref/ChromaticPolynomial.html}, note=[Accessed: 13-June-2026]}