4
$\begingroup$

The odd girth of a graph $G$ is defined as the minimum length of an odd cycle in $G$. Let $n_g(k)$ denote the minimum number of vertices in a $k$-chromatic graph of odd girth $g$. What are the known upper and lower bounds on $n_g(k)$?

It is known that the order of magnitude of $n_5(k)$ is $k^2 \log k$; this corresponds to $k$-chromatic triangle-free graphs. Is anything known for higher values of $g$?

$\endgroup$

1 Answer 1

4
$\begingroup$

In this paper (also available here) we show that a graph having no odd cycles of length $\leq 2r-1$ and having at most $$ \frac{(k+r)(k+r+1)\dots(k+2r-1)}{2^{r-1}r^r} $$ vertices is properly $k$-colorable. This provides an upper bound.

Another upper bound is provided by the paper by Kierstead, Szemeredi, and Trotter (see reference [4] in the above paper --- this also contains some upper bounds!).

On the upper bounds --- there are several different examples. One is the Schrijver subgraph of the Kneser graph (see [6] in the mentioned paper, or discussion on the first page), another one is the iterated (generalized) Mycielski construction applied to $C_{2r+1}$; see a relate discussion in

A. Gyarfas, T. Jensen, and M. Stiebitz, On graphs with strongly independent color-classes. // Journal of Graph Theory 46 (2004), 1–14.

$\endgroup$
2
  • $\begingroup$ Thanks for the nice answer! The expression you give provides a lower bound, not an upper bound, right? So, as far as you know, the best upper bound comes from Schrijver graphs? $\endgroup$ Oct 31, 2018 at 16:43
  • $\begingroup$ Right,, it provides a lower bound. Both Schrijver and (generalized) Mycielski provide an upper bound which seems to be tight in the exponent of $k$ (when $k$ is large compared with $r$), due to Kierstead--Szemeredi--Trotter. For other relations of parameters, I do not remember... By the way, you may find some extra links to some results for specific series of parameters in the Intro of arxiv.org/pdf/1401.8086.pdf $\endgroup$ Oct 31, 2018 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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