𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fragmentability of Graphs

✍ Scribed by Keith Edwards; Graham Farr

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
128 KB
Volume
82
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Achromatic number of fragmentable graphs
Achromatic number of fragmentable graphs
✍ Keith Edwards πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 175 KB

## Abstract A __complete coloring__ of a simple graph __G__ is a proper vertex coloring such that each pair of colors appears together on at least one edge. The __achromatic number__ ψ(__G__) is the greatest number of colors in such a coloring. We say a class of graphs is fragmentable if for any po

Fragments in kcritical n-connected graph
Fragments in kcritical n-connected graphs
✍ Su Jianji πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 413 KB

## Abstract Madar conjectured that every __k__‐critical __n__‐connected non‐complete graph __G__ has (2__k__ + 2) pairwise disjoint fragments. We show that Mader's conjecture holds if the order of __G__ is greater than (__k__ + 2)__n__. From this, it implies that two other conjectures on __k__‐crit

Fragments in 2-Critically n-Connected Gr
Fragments in 2-Critically n-Connected Graphs
✍ J.J. Su πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 428 KB

Mader conjectured that every non-complete \(k\)-critically \(n\)-connected graph has \((2 k+2)\) pairwise disjoint fragments. The conjecture was verified by Mader for \(k=1\). In this paper, we prove that this conjecture holds also for \(k=2\). 1993 Academic Press. Inc.

Maximum acyclic and fragmented sets in r
Maximum acyclic and fragmented sets in regular graphs
✍ Penny Haxell; Oleg Pikhurko; Andrew Thomason πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 126 KB

## Abstract We show that a typical __d__‐regular graph __G__ of order __n__ does not contain an induced forest with around ${2 {\rm In} d \over d}$ vertices, when __n__ ≫ __d__ ≫ 1, this bound being best possible because of a result of Frieze and Łuczak [6]. We then deduce an affirmative answer to

Graphs omitting sums of complete graphs
Graphs omitting sums of complete graphs
✍ Cherlin, Gregory; Shi, Niandong πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 119 KB πŸ‘ 2 views

For every finite m and n there is a finite set {G 1 , . . . , G l } of countable (m β€’ K n )-free graphs such that every countable (m β€’ K n )-free graph occurs as an induced subgraph of one of the graphs G i .