On graphs all of whose \(\{C_3,T_3\}\)-free arc colorations are kernel-perfect (Q2773044)

A digraph \(D=(V,A)\) is called a KP-digraph if every induced subdigraph of \(D\) has a kernel. Let the arcs of \(D\) be \(m\)-coloured with exactly \(m\) different colours. The closure of \(D\) is defined as the \(m\)-coloured digraph \(\zeta(D)=(V,B)\) where \((u,v)\in B\) whenever there exists a monochromatic path from \(u\) to \(v\) in \(D\) (the arc \((u,v)\) is coloured with the colour of the corresponding path). Let \(T_3\) denote the class of all 3-coloured transitive tournaments of order 3 and let \(C_3\) denote the class of all 3-coloured directed cycles of order 3. NEWLINENEWLINENEWLINEThe authors define an \(m\)-orientation-coloration of a simple graph \(G\) as an \(m\)-coloured digraph representing an asymmetric orientation of \(G.\) They study the class \(E\) of all such graphs \(G\) so that for any \((T_3\cup C_3)\)-free \(m\)-orientation-coloration \(D\) of \(G\) the closure \(\zeta(D)\) is a KP-digraph. It is proved that: (1) the class \(E\) is additive and inductively hereditary; (2) every connected graph \(G\in E\) is triangulated; and (3) if \(G\) is a Hamiltonian graph belonging to \(E,\) then the complement of \(G\) has at most one nontrivial component (\(K_3\) or a star).