planar graph and its complement

Question

Prove that there is no 9-vertex planar graph $G$, such that the chromatic polynomial of $G$ is equal to the chromatic polynomial of $\overline{G}$. >

The chromatic polynomial of graphs is defined here.

I thought that maybe we can use Kuratowski's theorem, but I do not know how. Actually, because this theorem gives a straightforward condition for a graph to be planar, I tried to use contradiction and the use this theorem, but I got confused.

Note: The graph should not necessarily be connected.

Answer 1

You'll have some difficulty, because such a graph does exist. The planar graph below and its complement both have chromatic polynomial $$x^9-18 x^8+141 x^7-627 x^6+1728 x^5-3015 x^4+3242 x^3-1956 x^2+504 x.$$

Found by downloading the $71885$ connected planar graphs from here, and checking the $18$-edge ones for the chromatic polynomial condition using Mathematica. There are a total of $19$ examples.

If anyone wants to check my work, the graph6 code for this graph is >>graph6<<H?C^L\v. For example, the following Mathematica code will do:

graph = ImportString[">>graph6<<H?C^L\\v"]
PlanarGraphQ[graph]
ChromaticPolynomial[graph, x]
ChromaticPolynomial[GraphComplement[graph], x]

---

However, there are no possible examples with more than $9$ vertices. The reason is that the chromatic polynomial of a $n$-edge, $m$-vertex graph begins with $x^n - m x^{n-1}$, followed by lower-order terms. So if $G$ and $\overline{G}$ have the same chromatic polynomial, they both have the same number of edges: $\frac12 \binom n2$.

For $n=10$, this requires having $22.5$ edges, which is impossible. For $n \ge 11$, the required number of edges exceeds $3n-6$: the most edges that a planar graph can have.