Fragmentability of graphs

Keith Edwards, Graham Farr

    Research output: Contribution to journalArticle

    20 Citations (Scopus)

    Abstract

    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
    Volume82
    Issue number1
    DOIs
    Publication statusPublished - May 2001

      Fingerprint

    Keywords

    • Fragmentability
    • Planarisation
    • Component

    Cite this