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

$\endgroup$
7
  • 3
    $\begingroup$ 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}$. $\endgroup$
    – user83827
    Nov 2, 2011 at 19:46
  • 2
    $\begingroup$ 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). $\endgroup$
    – user83827
    Nov 2, 2011 at 19:54
  • $\begingroup$ ccc, thanks, these comments are great. If you would copy them into an answer I'd be happy to accept it. $\endgroup$ Nov 2, 2011 at 20:05
  • $\begingroup$ 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$ $\endgroup$ Nov 2, 2011 at 20:06
  • $\begingroup$ 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?) $\endgroup$ Nov 2, 2011 at 20:27

2 Answers 2

7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .