The chromatic number of a graph is at most its circumference: the length of the longest cycle in the graph. (Making an exception for forests, where the chromatic number is at most $2$ and the circumference is undefined.)
This can be shown as a corollary of the following theorem:
If $G$ has $k$ distinct odd cycle lengths and $k'$ distinct even cycle lengths, then $\chi(G) \le k+k'+2$.
(P. Mihók, I. Schiermeyer, Cycle lengths and chromatic number of graphs, Discrete Math. 286 (2004) 147–149.)
If we assume that the longest cycle in $G$ has length $\ell$, then there are $\ell-2$ possible cycle lengths: $\{3, 4, \dots, \ell-1,\ell\}$. Therefore $k+k'\le \ell-2$, so by the theorem above $\chi(G) \le \ell$.
My question is this: does this statement have an easier proof? After all, the inequality between the chromatic number and the circumference is much weaker.
It is not hard to prove in the case $\ell=3$ (as seen in this recent question).
Also, there is a short argument that any graph $G$ with $\chi(G)=k$ contains a path (not a cycle) on $k$ vertices: let the colors be $\{1,2,\dots,k\}$, choose a coloring such that any vertex of color $i$ is adjacent to vertices $1,2,\dots,i-1$ (for instance, the coloring that minimizes the sum of colors over all vertices will work). Then from a vertex of color $k$, we can go to a vertex of color $k-1$, from there to a vertex of color $k-2$, and so on until we get to a vertex of color $1$.
Best Answer
After some more thinking, I found a simple solution. We get it very quickly from two results which are well-known in graph theory, though for completeness I will include their proofs.
Proof. Take the longest path $v_0, v_1, v_2, \dots, v_\ell$ in $G$. The vertex $v_0$ has at least $k$ neighbors, and all of them must be other vertices on the path, because otherwise we could extend the path and make it even longer. The last of $v_0$'s neighbors on the path must be at least as far as $v_k$ (since there's $k$ of them), so we get a cycle of length at least $k+1$ by following the path from $v_0$ to $v_0$'s last neighbor, then taking the edge back to $v_0$.
Conversely, if the longest cycle in a graph $G$ has length $k$, then it has a vertex of degree $k-1$ or less. What's more, in every subgraph $H$ of $G$, the longest cycle has length $k$ or less (if it's a cycle in $H$, it's a cycle in $G$, too). So $H$ must have a vertex of degree $k-1$ or less.
A graph with this property - every subgraph has a vertex of degree $k-1$ or less - is called $(k-1)$-degenerate.
Proof. We induct on the number of vertices in $G$. When $G$ has $k$ vertices or fewer, we can $k$-color $G$ by giving all the vertices different colors.
Otherwise, let $v$ be a vertex of degree $k-1$ or less. $G-v$ is also $(k-1)$-degenerate (every subgraph of $G-v$ is a subgraph of $G$) and has one fewer vertex, so by induction $G-v$ is $k$-colorable. We can $k$-color $G$ by starting with the $k$-coloring of $G-v$, then giving $v$ a color distinct from the colors on its neighbors (which eliminates at most $k-1$ options).
Putting together the two lemmas: a graph with circumference $k$ is $(k-1)$-degenerate, so it has chromatic number at most $k$. The chromatic number is at most the circumference.