An intractability result for the vertex 3-colourability problem (Q2136878)

In this paper, the vertex 3-colorability problem is considered in a very special graph class denoted by \({\mathcal{X}}_9^\ast\). It is the class of all graphs in which any 5 vertices induce a subgraph that is either a forest, a line graph, a kite, a dart, a banner (\(P\)-graph), \(F_3+K_1\), \(W_4\) or \(C_5\), where \(F_n\) (\(W_n\)) denotes the fan graph (wheel) on \(n+1\) vertices and \(C_n\) denotes the cycle on \(n\) vertices. It is proved that the vertex 3-colorability problem is NP-complete in \({\mathcal{X}}_9^\ast\). The authors use a translation in which they start with the 4-regular graph \(G\) and obtain a graph \(G^\ast\in {\mathcal{X}}_9^\ast\) in the following way: for any vertex \(x \in V(G)\) with \(N_G(x)=\{x_1,x_2,x_3,x_4\}\) delete \(x\) and add edges \(x_it_i\) for any \(i \in \{1,2,3,4\}\), where \(t_1\), \(t_2\), \(t_3\), \(t_4\) are four vertices of a graph \(N\) (called necklace) that has two properties: \(\chi(N)=3\) and if \(c:V(N) \to \{1,2,3\}\) is an optimal vertex coloring, then \(c(t_1)=c(t_2)=c(t_3)=c(t_4)\).