Chromatic polynomial of planar graphs

260 Views Asked by At

The chromatic polynomial of a graph counts the number of its (proper) vertex k-colorings. (more details here)

Draw a planar graph $G$ with the maximum number of vertices such that the chromatic polynomial of $G$ is equal to the chromatic polynomial of $\overline{G}$.

I can draw some examples which satisfy the condition but I do not know how to get to the graph with the maximum number of vertices which have the above feature.

1

There are 1 best solutions below

2
On

Let $n=\lvert G \rvert $ and $p_G(x)=\sum_{i=0}^n (-1)^i a_i x^{n-i}$ be the chromatic polynomial of $G$.

As you can see in the Wikipedia article that you linked (and you can prove by induction using the contraction-deletion relation) $a_1=e(G)$ is the number of edges in $G$.

Now observe that $e(G) + e(\bar{G})=\binom{n}{2}$ and since the chromatic polynomial is the same we mush have $e(G)=\frac{1}{2} \binom{n}{2}$.

But you know that $G$ is a planar graph and so $e(G) \leq 3n-6$. Solving the inequality $\frac{1}{2} \binom{n}{2} \leq 3n-6$ gives you $n\leq 10$. You can further eliminate $n=10$ because in this case $\binom{10}{2}$ is not divisible by $2$, so maximal such graph has at most $9$ vertices. From here on, finding a maximal example should be a matter of some casework.