# chromatic number of a graph versus its complement

What can be said about the rate of growth of $f(n)$, defined by $$f(n) = \min_{|V(G)|=n} \left[ \chi(G) + \chi(\bar{G}) \right],$$ where the minimum is taken over all graphs $G$ on $n$ vertices.

Two observations.

(1) Either $G$ or $\bar{G}$ contains a clique on roughly $\log{n}$ vertices by Ramsey theory, so $f(n) \ge c_1 \log n$ for some constant $c_1 > 0$.

(2) If $G = G(n,1/2)$ is a random graph, then $\chi(G) \approx \chi(\bar{G}) \approx n / \log{n}$ almost surely, so we also have $f(n) \le c_2 \, n/ \log n$ for some constant $c_2 > 0$.

These bounds seem hopelessly far apart.

Can we improve on the bounds $$c_1 \log n \le f(n) \le c_2 \, n / \log n$$ for all sufficiently large $n$?

-
By considering the disjoint union of $n$ cliques each of size $n$, you get $f(n^2) \leq 2n$, which improves the upper bound to something on the order of $\sqrt{n}$. –  user83827 Nov 2 '11 at 19:46
Oh, and this is probably optimal, since if $H$ is the complement of $G$, then $\chi(G)\chi(H) \geq n$ (if you associate with each vertex its two colors, no two vertices get the same pair). –  user83827 Nov 2 '11 at 19:54
ccc, thanks, these comments are great. If you would copy them into an answer I'd be happy to accept it. –  Matthew Kahle Nov 2 '11 at 20:05
The product $\chi(G)\chi(\bar G)$ must be at least $n$, since we can color $K_n$ with that many colors. So $\chi(G)+\chi(\bar G)\geq 2\sqrt n$ –  Thomas Andrews Nov 2 '11 at 20:06
From @ccc's comments, we know that $\lceil 2\sqrt{n} \rceil \leq f(n) \leq 2 \lceil \sqrt{n}\rceil$. This reduces to at most two values, but the question is, can we always get the smaller value? For example, is $f(12)=7$ or $f(12)=8$? (It's 7, but can we always get the smaller value?) –  Thomas Andrews Nov 2 '11 at 20:27

(Answering for posterity, don't select this as best.)

First, extend @ccc's proof to show that if $pq\geq n$ then $f(n)\leq p+q$. You do this first by taking a graph on $n$ nodes consisting of (at most) $p$ cliques of at most $q$ nodes each, and noting that $\chi(G)\leq p$ and $\chi(\bar G)\leq q$.

Now, as shown by ccc in coments above, $$\lceil 2\sqrt{n} \rceil \leq f(n) \leq 2 \lceil \sqrt{n}\rceil$$

This reduces to at most two values.

In general, if $\lceil 2x \rceil < 2\lceil x \rceil$, then the fractional part of $x$ is in $(0,\frac{1}{2})$. So we only need to consider the cases where the fractional part of $\sqrt n$ is in this range, that is, $\sqrt n =p + \delta$ where $p$ is an integer and $0<\delta<\frac{1}{2}$.

Claim: $p(p+1)\geq n$.

We know that $p(p+1)+\frac{1}{4}=(p+\frac{1}{2})^2>(p+\delta)^2=n$. Since $n$ and $p(p+1)$ are integers, this means $p(p+1)\geq n$.

Therefore, $f(n)\leq 2p+1 = \lceil 2\sqrt{n}\rceil$

So we know that $f(n)$ is always $\lceil 2\sqrt{n}\rceil$

-

If $G$ is a graph of order $n$, then

1. $2 \sqrt{n} \leq \chi(G) + \chi(\bar{G}) \leq n+1$
2. $n \leq \chi(G) \cdot \chi(\bar{G}) \leq \left(\frac{n+1}{2}\right)^2$

And, there is no possible improvement of any of these bounds. In fact, much more can be said:

Let $n$ be a positive integer. For every two positive integers $a$ and $b$ such that

1. $2 \sqrt{n} \leq a + b \leq n+1$
2. $n \leq a b \leq \left(\frac{n+1}{2}\right)^2$

there is a graph $G$ of order $n$ such that $\chi(G) = a$ and $\chi(\bar{G}) = b$.

Source: Graphs & Digraphs (Fifth edition) by Chartrand, Lesniak, and Zhang

-