Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
Oleg Veniaminovich Borodin · Journal of Graph Theory · 1996
If in a plane graph with minimum degree ≥3 no two triangles have an edge in common, then: (1) there are two adjacent vertices with degree sum at most 9, and (2) there is a face of size between 4 and 9 or a 10-face incident with ten 3-vertices. It follows that every planar graph without cycles between 4 and 9 is 3-colorable. © 1996 John Wiley & Sons, Inc.