Galeana-Sánchez, Hortensia; García-Ruvalcaba, José de Jesús On graphs all of whose \(\{C_3,T_3\}\)-free arc colorations are kernel-perfect. (English) Zbl 0990.05060 Discuss. Math., Graph Theory 21, No. 1, 77-93 (2001). 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. The 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). Reviewer: Matúš Harminc (Košice) Cited in 3 Documents MSC: 05C20 Directed graphs (digraphs), tournaments Keywords:kernel-perfect digraph; \(m\)-coloured digraph PDFBibTeX XMLCite \textit{H. Galeana-Sánchez} and \textit{J. de J. García-Ruvalcaba}, Discuss. Math., Graph Theory 21, No. 1, 77--93 (2001; Zbl 0990.05060) Full Text: DOI