Xu–Liu conjecture on degree sequences of chromatically equivalent complements

Let GG be a simple graph, let pG(k)p_G(k) denote its chromatic polynomial, and let G\overline{G} denote its complement. Suppose that

pG(k)=pG(k).p_G(k)=p_{\overline{G}}(k).

Xu–Liu conjecture. Then GG and G\overline{G} have the same degree sequence. This conjecture concerns graphs whose chromatic polynomial agrees with that of their complement. The paper disproves it by constructing infinitely many graphs with the stated chromatic-polynomial property but different degree sequences from their complements.

Sources & referencesView supporting material

Primary source

Jernej Azarija, “Tutte polynomials and a stronger version of the Akiyama-Harary problem”, arXiv:1306.0864 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.