Borodin, O. V. Structural properties of plane graphs without adjacent triangles and an application to 3-colorings. (English) Zbl 0838.05039 J. Graph Theory 21, No. 2, 183-186 (1996). It is shown that for a plane graph of minimum degree at least 3 without two triangles with an edge in common, there are two adjacent vertices with degree sum at most 9 and there is a face of dual degree between 4 and 9 or a 10-face incident with ten 3-vertices. Based on this, it follows that every planar graph without cycles between 4 and 9 is 3-colorable. Reviewer: Liu Yanpei (Beijing) Cited in 4 ReviewsCited in 63 Documents MSC: 05C10 Planar graphs; geometric and topological aspects of graph theory 05C15 Coloring of graphs and hypergraphs Keywords:3-coloring; plane graph; triangles PDFBibTeX XMLCite \textit{O. V. Borodin}, J. Graph Theory 21, No. 2, 183--186 (1996; Zbl 0838.05039) Full Text: DOI