Decomposing a planar graph of girth 5 into an independent set and a forest (Q1026008)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposing a planar graph of girth 5 into an independent set and a forest |
scientific article |
Statements
Decomposing a planar graph of girth 5 into an independent set and a forest (English)
0 references
23 June 2009
0 references
\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.
0 references
planar graphs of girth 5
0 references
independent sets
0 references
forests
0 references