Maximum induced forests of planar graphs (Q1107540)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Maximum induced forests of planar graphs
scientific article

    Statements

    Maximum induced forests of planar graphs (English)
    0 references
    0 references
    0 references
    1987
    0 references
    We propose following two conjectures: 1) If G is a planar graph of order \(n\geq 4\), then there exist \(\lceil \frac{n}{2}\rceil\) vertices in G which induce a forest. 2) If G is a planar graph of order n, then it has a stable set with \(\lceil \frac{n}{4}\rceil\) vertices.
    0 references
    planar graph
    0 references
    forest
    0 references
    stable set
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references