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
    0 references
    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

    Identifiers