2019/07/11 by S.A. Choudum, Choudum, S. A., T. Karthick +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1907.05018
openalex publication_date 2019/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that every connected induced subgraph of a graph G is dominated by an induced connected split graph if and only if G is \calC-free, where \calC is a set of six graphs which includes P7 and C7, and each containing an induced P5. A similar characterisation is shown for the class of graphs which are dominated by induced complete split graphs. Motivated by these results, we study structural descriptions of some classes of \calC-free graphs. In particular, we give structural descriptions for the class of (P7,C7,C4,gem)-free graphs and for the class of (P7,C7,C4,diamond)-free graphs. Using these results, we show that every (P7,C7,C4,gem)-free graph G satisfies χ(G) ≤ 2ω(G)-1, and that every (P7,C7,C4,diamond)-free graph H satisfies χ(H) ≤ ω(H)+1. These two upper bounds are tight for any subgraph of the Petersen graph containing a C5.