[Math] Chromatic number of complement of bipartite graph

coloringgraph theory

What is the chromatic number of the complement of bipartite graph on $n$ vertices?

If I have a complete bipartite graph $K_{1,n-1}$, then its complement are two disconnected complete graphs, $K_1$ and $K_{n-1}$. Then the complement cannot be colored with less than $n-1$ colors.

But what is the minimal chromatic number of the complement?

Thank for your advices.

Best Answer

A bipartite graph with $2n$ vertices will have :

  • at least no edges, so the complement will be a complete graph that will need $2n$ colors
  • at most complete with two subsets. The complement will be two complete graphs of size $k$ and $2n-k$. Then, it will need $\max(k,2n-k)$ colors, and the minimum is obtained for $k=n$, and it will need exactly $n$ colors.
Related Question