2019/03/31 by Ringi Kim, Sergey Norin, Sang-il Oum +1
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Combinatorics #Digital Image Processing Techniques #Discrete mathematics #Graph #Indifference graph #Limits and Structures in Graph Theory #Line graph #Mathematics #Pathwidth #Vertex (graph theory) #math.CO #msc:05C70
paper · pdf · doi:10.1016/j.dam.2020.09.006
28 pages, 8 figures. Accepted to Discrete Appl. Math., 2020
openalex publication_date 2020/09/26 · arxiv created 2020/11/04 · arxiv updated 2020/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
For a class C of graphs, we define C-edge-brittleness of a graph G as the minimum ℓ such that the vertex set of G can be partitioned into sets inducing a subgraph in C and there are ℓ edges having ends in distinct parts. We characterize classes of graphs having bounded C-edge-brittleness for a class C of forests or a class C of graphs with no K4∖e topological minors in terms of forbidden obstructions. We also define C-vertex-brittleness of a graph G as the minimum ℓ such that the edge set of G can be partitioned into sets inducing a subgraph in C and there are ℓ vertices incident with edges in distinct parts. We characterize classes of graphs having bounded C-vertex-brittleness for a class C of forests or a class C of outerplanar graphs in terms of forbidden obstructions. We also investigate the relations between the new parameters and the edit distance.