2013/02/04 by Maria Chudnovsky, Chudnovsky, Maria, Alex Scott +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1302.0812
arxiv created 2013/02/04 · openalex publication_date 2013/02/04 · arxiv updated 2013/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
For a graph G and a set of graphs H, we say that G is \em H-free if no induced subgraph of G is isomorphic to a member of H. Given an integer P>0, a graph G, and a set of graphs F, we say that G \em admits an (F,P)-partition if the vertex set of G can be partitioned into P subsets X1,..., XP, so that for every i ∈ \1,..., P\, either |Xi|=1, or the subgraph of G induced by Xi is \F\-free for some F ∈ F. Our first result is the following. For every pair (H,J) of graphs such that H is the disjoint union of two graphs H1 and H2, and the complement Jc of J is the disjoint union of two graphs J1c and J2c, there exists an integer P>0 such that every \H,J\-free graph has an (\H1,H2,J1,J2\,P)-partition. Using a similar idea we also give a short proof of one of the results of \citeheroes. Our final result is a construction showing that if \H,J\ are graphs each with at least one edge, then for every pair of integers r,k there exists a graph G such that every r-vertex induced subgraph of G is \H,J\-split, but G does not admits an (\H,J\,k)-partition.