Every planar graph without adjacent short cycles is 3-colorable
Tao Wang
所有作者
Tao Wang
文献摘要
Two cycles are {\em adjacent} if they have an edge in common. Suppose that
G is a planar graph, for any two adjacent cycles C1 and C2, we have
∣C1∣+∣C2∣≥11, in particular, when ∣C1∣=5, $|C_{2}| \geq
7.WeshowthatthegraphG$ is 3-colorable.