On graphs all of whose \C₃,T₃\-free arc colorations are kernel-perfect
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).
- Kernels in the closure of coloured digraphs
- Kernels by monochromatic paths and color-perfect digraphs
- Kernels in edge-coloured orientations of nearly complete graphs
- Cycles and transitivity by monochromatic paths in arc-coloured digraphs
- Kernels by monochromatic directed paths in 3-colored tournaments and quasi-tournaments
This page was built for publication: On graphs all of whose \(\{C_3,T_3\}\)-free arc colorations are kernel-perfect
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2773044)
