Coloring of \((P_5, 4\)-wheel)-free graphs (Q2113346)

A hereditary (i.e. closed under taking subgraphs) family \(\mathcal{C}\) of graphs has a \(\chi\)-binding function \(f\) if, for any \(G \in \mathcal{C}\), it holds that \(\chi(G) \leq f(\omega(G))\). Here, \(\chi(G)\) and \(\omega(G)\) are the chromatic number of \(G\) and the clique number of \(G\) (the size of a maximum clique of \(G\)) respectively. The article provides a new \(\chi\)-binding function for the family of \((P_5, W_4)\)-free graphs. Here, \(P_5\) is the path on five vertices, and \(W_4\) is the \(4\)-wheel, the graph obtained from a cycle on \(4\) vertices after adding a new vertex adjacent to all the vertices of the cycle; and a graph is \((P_5, W_4)\)-free if it does not contain any of \(P_5\) or \(W_4\) as induced subgraphs. The main result of the paper says that for any \((P_5, W_4)\)-free graph \(G\), it holds that \(\chi(G) \leq 3 \omega(G)/2\) (or equivalently, \(f(x) = 3x/2\) is a \(\chi\)-binding function for the family of \((P_5, W_4)\)-free graphs). This is the best \(\chi\)-binding function for the family \((P_5, W_4)\)-free graphs known so far. It also provides better \(\chi\)-binding functions for families of graphs where \(\chi\)-binding functions were already known, e.g. for the family of \((3 K_1, W_4)\)-free graphs [\textit{S. A. Choudum} et al., Graphs Comb. 24, No. 5, 413--428 (2008; Zbl 1190.05066)]. The main result is also complemented with examples of \((P_5, W_4)\)-free graphs \(G\) which satisfy \(\chi(G) \geq 10 \omega(G)/7\). The proof follows from a structural description of \((P_5, W_4)\)-free graphs, which is the main technical result of the paper. An atom is a graph without a clique cutset (a clique whose removal increases the number of connected components). A quasi-line graph is a graph \(G\) where the neighbourhood \(N(v)\) of any vertex \(v \in V(G)\) can be expressed as the union of two cliques. A graph \(G\) is said to be nice if there exist three stable sets (independent sets) \(S_1\), \(S_2\), \(S_3\) whose removal decreases the clique number of \(G\) by at least \(2\). The main structural result claims that any connected \((P_5, W_4)\)-free atom \(G\) must be a perfect graph, a nice graph, or a quasi-line graph.