On graphs with no induced five‐vertex path or paraglider. Issue 2 (19th January 2021)

• Record Type: Journal Article
• Authors: Huang, Shenwei; Karthick, T.
• Is Part Of: Journal of graph theory. Volume 97:Issue 2(2021)
• Page Start: 305
• Page End: 323
• Publication Date: 2021-01-19
• Subjects: chromatic number -- clique number -- P5‐free graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22656
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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 for the chromatic number of ( P 5, paraglider)‐free graphs for any ϵ > 0 .