Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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
2  
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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