On graphs with no induced five‐vertex path or paraglider
Shenwei Huang, T. Karthick · Journal of Graph Theory · 2021
Abstract Given two graphs and , a graph is ‐free if it contains no induced subgraph isomorphic to or . For a positive integer , is the chordless path on vertices. A paraglider is the graph that consists of a chorless cycle plus a vertex adjacent to three vertices of the . In this paper, we study the structure of (, paraglider)‐free graphs, and show that every such graph satisfies , where and are the chromatic number and clique number of , respectively. Our bound is attained by the complement of the Clebsch graph on 16 vertices. More strongly, we completely characterize all the (, paraglider)‐free graphs that satisfies . We also construct an infinite family of (, paraglider)‐free graphs such that every graph in the family has . This shows that our upper bound is optimal up to an additive constant and that there is no ‐approximation algorithm for the chromatic number of (, paraglider)‐free graphs for any .