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?



chromatic number of a simple graph whose length of the longest odd cycle is 2k+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.](http://www.sciencedirect.com/science/article/pii/0012365X9290037G#)


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.](http://onlinelibrary.wiley.com/doi/10.1002/jgt.20209/abstract)




---


**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.](http://www.sciencedirect.com/science/article/pii/S0012365X04002249#)


