On the divisibility of graphs (Q5957752)

For a simple graph \(G=(V,E)\) and a vertex \(x \in V\), let \(H_1,H_2,\ldots ,H_k\) be the \(k\) \((\geq 1)\) components of the neighborhood \(N(x)\) of \(x\) in \(G\). Then the graph \(G_x\) is obtained from \(G\) by the transformation of removing \(x\) and adding \(k\) new non-adjacent vertices \(x_1,x_2,\ldots ,x_k\) (called copies of \(x\)) and making each \(x_i\) adjacent to all vertices in \(H_i\) \((1\leq i \leq k)\). In the resulting graph \(G_x\), the neighborhood of each copy \(x_i\) of \(x\) is connected. Using this transformation repeatedly one gets a graph \(\widetilde{G}\) in which no vertex has a disconnected neighborhood. The construction of \(\widetilde{G}\) takes \(O(|V|^2+ |V||E|)\) time and \(\omega(G) = \omega (\widetilde{G})\), where \(\omega \) is the clique number. A cricket is the graph consisting of a triangle with two pendant edges at one vertex of the triangle. The authors prove that for a cricket-free graph \(G\) without odd holes, \(\chi (G) \chi (\widetilde{G})\), where \(\chi \) is the chromatic number. A gem is \(K_1 \vee P_4\) and let \(F_1\) be the graph obtained by identifying an edge of \(K_4\) with an edge of another \(K_4\). The authors prove that the clique number of \((\text{gem},F_1)\)-free graphs can be computed in \(O(|V|^2+|V||E|)\) time. This class strictly contains the diamond-free graphs. They further deduce the validity of the strong perfect graph conjecture (SPGC) for (cricket, gem, \(F_1\))-free graphs. Let \( F_2 = K_2\vee \overline{K}_3,\;F_4 = K_1\vee P_5\) and \(F_3\) be obtained by identifying two adjacent edges of a \(K_4\) with an edge each of two different triangles. All these graphs and the cricket contain a claw. The authors prove that the SPGC is true for \((\text{cricket},F_2,F_3,F_4)\)-free graphs, thus extending the result for claw-free graphs.