zbMATH — the first resource for mathematics

Structural properties of plane graphs without adjacent triangles and an application to 3-colorings. (English) Zbl 0838.05039
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.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI