On graphs with no induced five-vertex path or paraglider

MaRDI QIDQ6316256zbMATH OpenFDO

Authors Shenwei Huang, T. Karthick

Publication date 27 March 2019

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 $chi(G)lelceilfrac32omega(G)ceil$, 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)>frac32omega(G)$. We also construct an infinite family of ($P_5$, paraglider)-free graphs such that every graph $G$ in the family has $chi(G)=lceilfrac32omega(G)ceil-1$. This shows that our upper bound is optimal up to an additive constant and that there is no $(frac32-epsilon)$-approximation algorithm to the chromatic number of ($P_5$, paraglider)-free graphs for any $epsilon>0$.

This page was built for publication: On graphs with no induced five-vertex path or paraglider

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6316256)