# What can be said about the rate of growth of f(n), defined by f(n)=min/(|V(G)|=n) [χ(G)+χ(bar G)], where the minimum is taken over all graphs G on n vertices.

chromatic number of a graph versus its complement
What can be said about the rate of growth of f(n), defined by
$f\left(n\right)=\underset{|V\left(G\right)|=n}{min}\left[\chi \left(G\right)+\chi \left(\overline{G}\right)\right],$
where the minimum is taken over all graphs G on n vertices.
Two observations.
(1) Either G or $\overline{G}$ contains a clique on roughly logn vertices by Ramsey theory, so $f\left(n\right)\ge {c}_{1}\mathrm{log}n$ for some constant ${c}_{1}>0$.
(2) If G=G(n,1/2) is a random graph, then $\chi \left(G\right)\approx \chi \left(\overline{G}\right)\approx n/\mathrm{log}n$ n/ log n almost surely, so we also have $f\left(n\right)\le {c}_{2}\phantom{\rule{thinmathspace}{0ex}}n/\mathrm{log}n$ n/log n for some constant ${c}_{2}>0$.
These bounds seem hopelessly far apart.
Can we improve on the bounds
${c}_{1}\mathrm{log}n\le f\left(n\right)\le {c}_{2}\phantom{\rule{thinmathspace}{0ex}}n/\mathrm{log}n$
for all sufficiently large n?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

frisiao
(Answering for posterity, don't select this as best.)
First, extend @ccc's proof to show that if $pq\ge n$ then $f\left(n\right)\le 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 \left(G\right)\le p$ and $\chi \left(\overline{G}\right)\le q$
Now, as shown by ccc in coments above,
$⌈2\sqrt{n}⌉\le f\left(n\right)\le 2⌈\sqrt{n}⌉$
This reduces to at most two values.
In general, if $⌈2x⌉<2⌈x⌉$, then the fractional part of x is in $\left(0,\frac{1}{2}\right)$. 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\left(p+1\right)\ge n$.
We know that $p\left(p+1\right)\ge n$. Since n and p(p+1) are integers, this means $p\left(p+1\right)\ge n$
Therefore, $f\left(n\right)\le 2p+1=⌈2\sqrt{n}⌉$
So we know that $f\left(n\right)$ is always $⌈2\sqrt{n}⌉$
###### Not exactly what you’re looking for?
Marisol Rivers
If G is a graph of order n, then
$2\sqrt{n}\le \chi \left(G\right)+\chi \left(\overline{G}\right)\le n+1$
$n\le \chi \left(G\right)\cdot \chi \left(\overline{G}\right)\le {\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
$2\sqrt{n}\le a+b\le n+1$
$n\le ab\le {\left(\frac{n+1}{2}\right)}^{2}$
there is a graph G of order n such that χ(G)=a and $pq\ge n$.
Source: Graphs & Digraphs (Fifth edition) by Chartrand, Lesniak, and Zhang