0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.