Mapping planar graphs to odd cycles

Importance: High ✭✭✭
Author(s): Jaeger, Francois
Subject: Graph Theory
» Coloring
» » Homomorphisms
Recomm. for undergrads: no
Posted by: mdevos
on: June 24th, 2007

\begin{conjecture} Every planar graph of girth $\ge 4k$ has a homomorphism to $C_{2k+1}$. \end{conjecture}

This conjecture is \OPrefnum[Jaeger's modular orientation conjecture]{130} restricted to planar graphs and then dualized. To see this duality, first note that circular coloring and circular flows are dual for planar graphs, and then observe that $(2k+1)$-orientations are equivalent to $2 + \frac{1}{k}$-flows and $2 + \frac{1}{k}$-colorings are equivalent to homomorphisms to $C_{2k+1}$. So if $G$ and $G^*$ are dual planar graphs, then we have the following equivalences.

\begin{enumerate} \item $G$ has a $(2k+1)$-orientation. \item $G$ has a $2 + \frac{1}{k}$-flow. \item $G^*$ has a $2 + \frac{1}{k}$-coloring. \item $G^*$ has a homomorphism to $C_{2k+1}$. \end{enumerate}

There is an easy family of graphs which show that the above conjecture (if true) is best possible. Let $H_k$ be the graph obtained from an odd circuit of length $4k-1$ by adding a new vertex $u$ joined to every existing vertex by a path of length $2k-1$. Now, $H_k$ is a planar graph of girth $4k-1$, but there is no homomorphism from $H_k$ to $C_{2k+1}$. To see the latter claim, suppose (for a contradiction) that such a homomorphsim $f$ exists, let $C$ be the unique circuit of $H_k \setminus u$ and let $a=f(u)$. Now, no vertex in $C$ can map to $a$ since every such vertex is distance $2k-1$ from $u$. However we must then have a homomorphism from $C$ to $C_{2k+1} \setminus a$, which is impossible since $C$ is an odd circuit and $C_{2k+1} \setminus u$ is bipartite.

The k=1 case of the above conjecture asserts that every (loopless) triangle free planar graph has a homomorphism to the triangle. In other words, every (loopless) triangle free planar graph is 3-colorable. This is a well known theorem of Grotszch. For every k>1, the above conjecture is still open. Actually, I think this conjecture is already quite interesting for k=2. One reason is that this case of the conjecture implies the 5-color theorem for planar graphs. To see this implication, suppose that the above conjecture is true for k=2, let G be a simple loopless planar graph, and let G' be the graph obtained from G by subdividing each edge two times. Now, G' has girth at least 9, so by our assumption there is a homomorphism from G' to C_5. It is easy to see that adjacent vertices of G must map to different vertices of C_5 under this homomorphism. Thus, we have a proper 5-coloring of G as desired.

Let us call a homomorphism to $C_{2k+1}$ a $C_{2k+1}$-\emph{coloring}. It is quite easy to show that every planar graph of girth > 10k has a $C_{2k+1}$-coloring. This follows from a simple degeneracy argument: Every such (nonempty) graph must have a either a vertex of degree $\le 1$, or a path $P$ of length $2k-1$ all of whose internal vertices have degree two. Both of these configurations are reducible, in the sense that we may delete either a vertex of degree $\le 1$ or the interior vertices of $P$ and then extend any $C_{2k+1}$-coloring of the resulting graph to a $C_{2k+1}$-coloring of the original. By more complicated, but similar degeneracy arguments, we can approach this conjecture. To my knowledge, the best result to date is as follows.

\begin{theorem}[Borodin, Kim, Kostochka, West] Every planar graph of girth $\ge \frac{20k-2}{3}$ has a homomorphism to $C_{2k+1}$. \end{theorem}

For the special case of the conjecture when $k=2$, Matt DeVos and Adam Deckelbaum have an unpublished improvement showing that every planar graph with odd girth $\ge 11$ has a homomorphism to $C_5$.


[BKKW] O. V. Borodin, S. J. Kim, A. V. Kostochka, D. B. West, Homomorphisms from sparse graphs with large girth. Dedicated to Adrian Bondy and U. S. R. Murty. J. Combin. Theory Ser. B 90 (2004), no. 1, 147--159. \MRhref{2041323}

[Ja] F. Jaeger, On circular flows in graphs in Finite and Infinite Sets, volume 37 of Colloquia Mathematica Societatis Janos Bolyai, edited by A. Hajnal, L. Lovasz, and V.T. Sos. North-Holland (1981) 391-402.

[Zh] X. Zhu, Circular chromatic number of planar graphs of large odd girth, Electronic Journal of Combinatorics Vol. 8 no. 1 (2001).

* indicates original appearance(s) of problem.