Skip to main content
2 of 2
added 833 characters in body
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

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.

Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43