Is there a general way to define a lower bound on $|V(G)|$ given the girth $g(G)=g$ and chromatic number $\chi(G) = k$?
I heard there is a result, telling that $|V(G)| \geq k^{\frac{g}{2}}$, but I can't find it.
Thanks in advance.
Is there a general way to define a lower bound on $|V(G)|$ given the girth $g(G)=g$ and chromatic number $\chi(G) = k$?
I heard there is a result, telling that $|V(G)| \geq k^{\frac{g}{2}}$, but I can't find it.
Thanks in advance.
Some such lower bound may exist, but the inequality $\chi(G)^{g(G)} \leq n$ is very far from being true in general.
For one example, let $n \geq 3$ and let $G = K_n$. Then $\chi(G) = n$ and $g(G) = 3$, but $n^{3/2} > n$.
For another, let $n \geq 3$ and let $G = C_{2n}$. Then $\chi(G) = 2$ and $g(G) = 2n$, but $2^n > 2n$.