Fragmentability of graphs

Keith Edwards, Graham Farr

    Research output: Contribution to journalArticlepeer-review

    22 Citations (Scopus)


    We define a parameter which measures the proportion of vertices which must be removed from any graph in a class in order to break the graph up into small (i.e. bounded sized) components. We call this the coefficient of fragmentability of the class. We establish values or bounds for the coefficient for various classes of graphs, particularly graphs of bounded degree. Our main upper bound is proved by establishing an upper bound on the number of vertices which must be removed from a graph of bounded degree in order to leave a planar graph.
    Original languageEnglish
    Pages (from-to)30-37
    Number of pages8
    JournalJournal of Combinatorial Theory, Series B
    Issue number1
    Publication statusPublished - May 2001


    • Fragmentability
    • Planarisation
    • Component


    Dive into the research topics of 'Fragmentability of graphs'. Together they form a unique fingerprint.

    Cite this