Extreme Graph Theory. Chromatic number and girth

112 Views Asked by At

Find asymptotic lower estimate of function $$f(k):=\max_{G:\:|G|= k}(\operatorname{girth}(G)\cdot \chi(G)).$$

I tried to use Erdos theorem, that for every $k$, we can find the graph with $\chi(G) > k, \operatorname{girth}(G) > k$, but i couldn't done more. Any ideas?

1

There are 1 best solutions below

0
On

For $k\ge 3$ Look at the cycle graphs with $k$ vertices $C_k$ then $\chi(C_k)=\begin{cases}3 & \text{ if }k \text{ is odd}\\2 & \text{ if }k \text{ is odd} \end{cases}=\dfrac{5}{2}+\dfrac{(-1)^k}{2}$ and has girth $k$.

Thus $k\left(\dfrac{5}{2}+\dfrac{(-1)^k}{2}\right) \le f(k)$ for all $k\ge 3$

This works because $f(k)$ is the maximum of the expression over all graphs with $k$ vetices (containing a cycle i presume but the inequality is still true since $g=\infty$ if the graph is acyclic). Since $C_k$ is a graph with $k$ vertices for all $k\ge 3$ then $f(k)$ must be at least the value for this graph.

You can turn this in to an asymptotic bound by saying $f(k) = \Omega(k)$ using the Knuth definition of $\Omega$ because in particular $$2k\le k\left(\dfrac{5}{2}+\dfrac{(-1)^k}{2}\right) \le f(k)$$