Chromatically Equivalent Graphs

Two nonisomorphic graphs are said to be chromatically equivalent (also termed "chromically equivalent by Bari 1974) if they have identical chromatic polynomials. A graph that does not share a chromatic polynomial with any other nonisomorphic graph is said to be a chromatically unique graph.


The chromatically equivalent simple graphs on five or fewer vertices are illustrated above.

Bari (1974) gives a number of chromatically equivalent graph pairs on 11 to 17 vertices that are planar triangulations.

It appears to be the case that all resistance-equivalent graphs are also chromatically equivalent.

See also

Chromatic Polynomial, Chromatically Unique Graph, Resistance-Equivalent Graphs

Explore with Wolfram|Alpha


Bari, R. A. "Chromatically Equivalent Graphs." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 186-200, 1974.Bari, R. A. "Recent Results on Chromatically Equivalent Graphs." In Second International Conference on Combinatorial Mathematics (New York, 1978). Ann. New York Acad. Sci. 319, 37-46, 1979.

Referenced on Wolfram|Alpha

Chromatically Equivalent Graphs

Cite this as:

Weisstein, Eric W. "Chromatically Equivalent Graphs." From MathWorld--A Wolfram Web Resource.

Subject classifications