Kernels in edge-coloured orientations of nearly complete graphs
The digraph \(D\) is an orientation of a graph \(G\) if \(D\) is obtained from \(G\) by the orientation of each edge of \(G\) in exactly one of the two possible directions. The digraph \(D\) is an \(m\)-colored digraph if the arcs of \(D\) are colored with \(m\)-colors. A directed path or a directed cycle is said to be monochromatic if all of its arcs are colored alike. The paper gives sufficient conditions for an \(m\)-colored orientation of a graph obtained from the \(n\)-vertex complete graph by the deletion of \(r\) arcs all of them incident with a vertex \(x\), \(r < n\), to have a kernel by monochromatic paths.
scientific article; zbMATH DE number 5321333