Decomposing a planar graph of girth 5 into an independent set and a forest (Q1026008): Difference between revisions

\textit{O. V. Borodin} and \textit{A. N. Glebvov} [Diskretn. Anal. Issled. Oper., Ser. 1 8, No. 4, 34--53 (2001; Zbl 1012.05133)] showed that the vertex set of every planar graph of girth at least five can be partitioned into an independent set and a set inducing a forest. The present authors use a list-coloring technique to extend that result and then apply that extension to extend also the theorem of Grötzsch stating that every triangle-free graph is 3-colorable. This latter extension allows an unbounded number of triangles. Specifically, the extension assumes that \(G\) is a plane graph such that the distance between any two triangles is a least 4 and that each triangle contains a vertex which is on the outer face boundary and is not in any 4-cycle. The conclusion is that \(G\) has chromatic number at most 3.