chromatic number of a simple graph whose length of the longest odd cycle is 2k+1

Question

Let $G$ be a simple graph and the length of the longest odd cycle of $G$ is $2k+1$,then I guess the chromatic number of $G$ is no more than $2k+2$,is it right?

Answer 1

Yes. If a graph $G$ is bipartite, by definition its chromatic number $\chi(G)$ is less than or equal to $2$. If $G$ contains an odd cycle, then $\chi(G) \leq l+1$, where $l$ is the length of a longest odd cycle. I found a couple papers that attribute this result to Erdős and Hajnal, but don't quote me on this. You can find a proof of a slightly stronger theorem here:

A. Gyárfás, Graphs with k odd cycle lengths, Discrete Math. 103 (1992) 41–48.

The result there states that $\chi(G) \leq 2k+2$, where $k$ is the cardinality of the set $L(G) = \{i \mid \text{$G$ contains a cycle of length $2i+1$}\}$, which is best possible because of the case $G = K_{2k+2}$.

Even stronger results can be found here:

S. Kenkre, S. Vishwanathan, A bound on the chromatic number using the longest odd cycle length, J. Graph Theory, 54 (2007) 267–276.

---

Edit: Regarding the question about a possible extension to the even cycle case asked in the comment below, there is such a theorem generalizing Gyárfás's result:

Let $L_{\text{o}}(G) = \{2i+1 \mid \text{$G$ contains a cycle of length $2i+1$}\}$ and $L_{\text{e}}(G) = \{2i \mid \text{$G$ contains a cycle of length $2i$}\}$, and write their cardinalities as $$\vert L_{\text{o}}(G)\vert = k$$ and $$\vert L_{\text{e}}(G)\vert = k'.$$ Then, for a simple finite graph $G$, $$\begin{align*}\chi(G) & \leq \min\{2k+2, 2k'+3\}\\ & \leq k+k'+2. \end{align*}$$

This is proved (Corollary 3) here:

P. Mihók, I. Schiermeyer, Cycle lengths and chromatic number of graphs, Discrete Math. 286 (2004) 147–149.

Answer 2

Yes it is right. Erdős and Hajnal proved this in 1966. Here is the paper: http://www.renyi.hu/~p_erdos/1966-07.pdf

You can find the claim as 'Theorem 7.7' in page 77.