Wheel-free graphs with no induced five-vertex path.
Arnab Char, T. Karthick · arXiv (Cornell University) · 2020
A $4$-wheel is the graph consisting of a chordless cycle on four vertices $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$. In this paper, we explore the structure of ($P_5$,$4$-wheel)-free graphs, and show that every such graph $G$ is either perfect, or a quasi-line graph, or has a clique cutset, or $G$ belongs to some well-defined special classes of graphs. This result enables us to show that every ($P_5$,$4$-wheel)-free graph $G$ satisfies $\chi(G)\leq \frac{3}{2}\omega(G)$. Moreover, this bound is asymptotically tight. That is, there is a class of ($P_5$,$4$-wheel)-free graphs $\cal H$ such that every graph $H\in \cal H$ satisfies $\chi(H)\geq\frac{10}{7}\omega(H)$.