Planarization and fragmentability of some classes of graphs (Q2427499)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Planarization and fragmentability of some classes of graphs
scientific article

    Statements

    Planarization and fragmentability of some classes of graphs (English)
    0 references
    13 May 2008
    0 references
    A graph \(G\) is \((C,\varepsilon)\)-fragmentable if there exists a \(X \subset V(G)\) such that \(|X|\leq \varepsilon|V(G)|\) and every component of \(G-X\) has at most \(C\) vertices. A class \(\Gamma\) of graphs is \(\varepsilon\)-fragmentable if there exists a \(C\) such that every \(G \in \Gamma\) is \((C,\varepsilon)\)-fragmentable. The coefficient of fragmentability of \(\Gamma\) is \(c_f (\Gamma)= \inf\{ \varepsilon\mid \Gamma\text{ is }\varepsilon\)-fragmentable
    0 references
    planarity
    0 references
    fragmentability
    0 references
    induced planar subgraph
    0 references
    series-parallel subgraphs
    0 references
    0 references
    0 references

    Identifiers