Fragmentability of classes of graphs

Graham Farr
School of Computer Science and Software Engineering Monash University, Victoria, Australia

We introduce the notion of fragmentability, which measures how easily the graphs in some class can be broken up into small (bounded size) pieces by removal of vertices. We focus on the proportion of vertices removed, rather than the difficulty of finding those vertices. We are particularly interested in classes of graphs of bounded degree, and find upper and lower bounds for such classes. The upper bound is obtained from an algorithm for obtaining a large induced planar subgraph of a graph.

(Joint work with Keith Edwards, University of Dundee.)