### Abstract

Fragmentability concerns the extent to which a graph can be broken up into small (bounded sized) components by removing as few vertices as possible. To make this concept precise, we define the coefficient of fragmentability of a class of graphs, and summarize the known upper and lower bounds for this parameter, for various graph classes. We discuss the relationship of fragmentability to the planarization of graphs (by removing vertices), and to colourings with small monochromatic components. We also mention a number of open problems and potential applications of fragmentability.

Original language | English |
---|---|

Title of host publication | Topics in Structural Graph Theory |

Editors | Lowell W. Beineke, Robin J. Wilson |

Publisher | Cambridge University Press |

Pages | 203-218 |

Number of pages | 16 |

ISBN (Print) | 978051802314 |

Publication status | Published - 2012 |

### Publication series

Name | Encyclopedia of Mathematics and Its Applications |
---|---|

Publisher | Cambridge University Press |

Volume | 147 |

## Fingerprint Dive into the research topics of 'Graph fragmentability'. Together they form a unique fingerprint.

## Cite this

Edwards, K., & Farr, G. (2012). Graph fragmentability. In L. W. Beineke, & R. J. Wilson (Eds.),

*Topics in Structural Graph Theory*(pp. 203-218). (Encyclopedia of Mathematics and Its Applications; Vol. 147). Cambridge University Press. http://www.cambridge.org/gb/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/topics-structural-graph-theory