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