9
$\begingroup$

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$?

  • 0
    Sorry, I was literally posting those comments on my way out the door (modern technology...). Anyway, Thomas Andrews' answer is more complete than my comments, so please feel free to accept it if you choose.2011-11-03

2 Answers 2

5

(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$

6

Although there is already an accepted answer, I answer to give a bit more information, for what I have to say would not fit in a comment.

This is the Nordhaus-Gaddum Theorem:

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