Graph fragmentability

Keith Edwards, Graham Farr

    Research output: Chapter in Book/Report/Conference proceedingChapter

    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 languageEnglish
    Title of host publicationTopics in Structural Graph Theory
    EditorsLowell W. Beineke, Robin J. Wilson
    PublisherCambridge University Press
    Pages203-218
    Number of pages16
    ISBN (Print)978051802314
    Publication statusPublished - 2012

    Publication series

    NameEncyclopedia of Mathematics and Its Applications
    PublisherCambridge University Press
    Volume147

    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