Every planar graph without adjacent short cycles is 3-colorable

Abstract

Two cycles are {\em adjacent} if they have an edge in common. Suppose that $G$ is a planar graph, for any two adjacent cycles $C_1$ and $C_2$, we have $|C_1|+|C_2|\ge 11$, in particular, when $|C_1|=5$, $|C_2|\ge 7$. We show that the graph $G$ is 3-colorable.

14 pages, 16 figures