On graphs with no induced five-vertex path or paraglider

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 chi(G) <= [ 3/2 omega(G)], where chi(G) and omega(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 chi(G) > 3/2 omega(G). We also construct an infinite family of (P-5, paraglider)-free graphs such that every graph G in the family has chi(G) = [3/2 omega(G)] -1. This shows that our upper bound is optimal up to an additive constant and that there is no (3/2-epsilon)-approximation algorithm for the chromatic number of (P-5, paraglider)-free graphs for any epsilon>0.

Automated summary

The paper investigates the structure of (P-5, paraglider)-free graphs, establishing a relationship between the chromatic number and clique number. It also characterizes graphs that satisfy certain conditions and shows the optimality of the upper bound. Additionally, it concludes that there is no (3/2-epsilon)-approximation algorithm for the chromatic number of (P-5, paraglider)-free graphs for any epsilon>0.