2019/03/27 by Shenwei Huang, Huang, Shenwei, T. Karthick +1
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.1903.11268
openalex publication_date 2019/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two graphs H1 and H2, a graph is (H1, H2)-free if it contains no induced subgraph isomorphic to H1 or H2. For a positive integer t, Pt is the chordless path on t vertices. A paraglider is the graph that consists of a chorless cycle C4 plus a vertex adjacent to three vertices of the C4. In this paper, we study the structure of (P5, paraglider)-free graphs, and show that every such graph G satisfies χ(G)≤ \lceil (3)/(2)ω(G) \rceil, where χ(G) and ω(G) are the chromatic number and clique number of G, respectively. Our bound is attained by the complement of the Clebsch graph on 16 vertices. More strongly, we completely characterize all the (P5, paraglider)-free graphs G that satisfies χ(G)> (3)/(2)ω(G). We also construct an infinite family of (P5, paraglider)-free graphs such that every graph G in the family has χ(G)=\lceil (3)/(2)ω(G) \rceil-1. This shows that our upper bound is optimal up to an additive constant and that there is no ((3)/(2)-ε)-approximation algorithm to the chromatic number of (P5, paraglider)-free graphs for any ε>0.