Decomposing a planar graph into degenerate graphs (Q1907105)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Decomposing a planar graph into degenerate graphs
scientific article

    Statements

    Decomposing a planar graph into degenerate graphs (English)
    0 references
    0 references
    27 June 1996
    0 references
    A graph \(G\) is \(k\)-degenerate if every subgraph of \(G\) has a vertex of degree less than \(k\). The author proves that the vertex set of any planar graph can be decomposed into two sets such that one of them induces a 3-degenerate graph and the other induces a 2-degenerate graph. He also proves that the vertex set of any planar graph can be decomposed into two sets each of which induces a subgraph with no cycle of length larger than three.
    0 references
    0 references
    0 references
    0 references
    0 references
    decomposition
    0 references
    \(k\)-degenerate
    0 references
    planar graph
    0 references
    0 references
    0 references