On graphs with no induced five-vertex path or paraglider
share
Given two graphs H_1 and H_2, a graph is (H_1, H_2)-free if it contains no induced subgraph isomorphic to H_1 or H_2. For a positive integer t, P_t is the chordless path on t vertices. A paraglider is the graph that consists of a chorless cycle C_4 plus a vertex adjacent to three vertices of the C_4. In this paper, we study the structure of (P_5, paraglider)-free graphs, and show that every such graph G satisfies χ(G)<3/2ω(G) , 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 (P_5, paraglider)-free graphs G that satisfies χ(G)> 3/2ω(G). We also construct an infinite family of (P_5, paraglider)-free graphs such that every graph G in the family has χ(G)=3/2ω(G) -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 (P_5, paraglider)-free graphs for any ϵ>0.
READ FULL TEXT