TOPICS
Search

Chromatically Equivalent Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Chromatically equivalent graphs are pairs of nonisomorphic graphs with identical chromatic polynomials. They are also called chromically equivalent (Bari 1974) or cochromatic. A graph that does not share a chromatic polynomial with any other nonisomorphic graph is said to be a chromatically unique graph.

ChromaticallyNonuniqueGraphs

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

References

Bari, R. A. "Chromatically Equivalent Graphs." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin, Germany: 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 Resource. https://mathworld.wolfram.com/ChromaticallyEquivalentGraphs.html

Subject classifications