Cycle Adjacency of Planar Graphs and 3-Colourability
Chung-Ying Yang, Xuding Zhu · Taiwanese Journal of Mathematics · 2011
Suppose $G$ is a planar graph. Let $H_G$ be the graph with vertex set $V(H_G) = \{ C:C$ is a cycle of G with $|C|\in \{4,6,7\} \}$ and $E(H_G) = \{ C_i C_j: C_i$ and $C_j$ are adjacent in $G\}$. We prove that if any $3$-cycles and $5$-cycles are not adjacent to $i$-cycles for $3 \leq i \leq 7$, and $H_G$ is a forest, then $G$ is $3$-colourable.