  Can a non self-complementary graph have the same chromatic polynomial as its
complement? The answer to this question of Akiyama and Harrary is positive and
was given by J. Xu and Z. Liu. They conjectured that every such graph has the
same degree sequence as its complement. In this paper we show that there are
infinitely many graphs for which this conjecture does not hold. We then solve a
more general variant of the Akiyama-Harary problem by showing that there exists
infinitely many non self-complementary graphs having the same Tutte polynomial
as their complements.
