Problem 14.4: Chromatic Equivalence
The question asked by J. Akiyama and F. Harary, if there
exists a graph that is chromatically equivalent to its
own complement without being self-complementary, which
was answered in a paper by K.M. Koh and K.L. Teo in 1991,
was answered independently by I.G. Dmitriev "Chromatic
Polynomials of Graphs (in Russian)" in: Methodical Direc-
tions for Students, Yakutsk, 1988 (Theorem 6 on page 15).
The complete answer to the question, namely that there
exists such a graph on n vertices if and only if n is at
least 8 and congruent to 0 or 1 modulo 4, was obtained
both by Dmitriev and by Koh and Teo.
We are grateful to O.V. Borodin for this information.
December 28, 1994. T.R. Jensen and B. Toft.
Last modified July 21, 1997 Bjarne Toft