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.

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.