2025/03/14 by Binlong Li, Li, Binlong, Ziqing Sang +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2503.11176
openalex publication_date 2025/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let F be a set of connected graphs, and let G be a graph. We say that G is \emphF-free if it does not contain F as an induced subgraph for all F\inF, and we call F a forbidden pair if |F|=2. A \varTheta-graph is the graph consisting of three internally disjoint paths with the same pair of end-vertices. If the \varTheta-subgraph T contains all vertices of G, then we call T a spanning \varTheta-subgraph of G. In this paper, we characterize all pairs of connected graphs R,S such that every 2-connected \R,S\-free graph has a spanning \varTheta-subgraph. In order to obtain this result, we also characterize all minimal 2-connected non-cycle claw-free graphs without spanning \varTheta-subgraphs.