Home » Subject » Graph Theory » Coloring » Homomorphisms

Mapping planar graphs to odd cycles

Importance: High ✭✭✭
Author(s): Jaeger, Francois
Subject: Graph Theory
» Coloring
» » Homomorphisms
Keywords: girth
homomorphism
planar graph
Recomm. for undergrads: no
Posted by: mdevos
on: June 24th, 2007
Conjecture   Every planar graph of girth $ \ge 4k $ has a homomorphism to $ C_{2k+1} $.

This conjecture is Jaeger's modular orientation conjecture 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.

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

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

Theorem  (Borodin, Kim, Kostochka, West)   Every planar graph of girth $ \ge \frac{20k-2}{3} $ has a homomorphism to $ C_{2k+1} $.

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

Related problems

Jaeger's modular orientation conjecture

Bibliography

[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. MathSciNet

[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.
add new comment