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$.


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.

Lemma 1. A graph $G$ with minimum degree $k$ contains a cycle of length at least $k+1$.

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.

Lemma 2. A $(k-1)$-degenerate graph $G$ has chromatic number at most $k$.

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.


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.