TOPICS
Search

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.

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: 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. https://mathworld.wolfram.com/ChromaticallyEquivalentGraphs.html

Subject classifications