Kernels by monochromatic directed paths in \(m\)-colored digraphs with quasi-transitive chromatic classes.
A digraph \(D\) is said to be \(m\)-coloured if the arcs of \(D\) are coloured using \(m\) colours. A non-empty set \(S \subseteq V(D)\) is said to be absorbent by monochromatic directed paths if, for every vertex \(u \in V(D) - S\), there exists \(v \in S\) such that \(u\) is joined to \(v\) by a directed path all of whose arcs are of the same colour. A set \(K \subseteq V(D)\) is called a kernel by monochromatic directed paths if:NEWLINENEWLINE(i) for every \(u,v \in K\) there is no monochromatic directed path between \(u\) and \(v\) andNEWLINENEWLINE(ii) for every \(x \in V(D)-K\) there exists \(y \in K\) such that \(x\) is joined to \(y\) by a monochromatic directed path.NEWLINENEWLINEFinally, a chromatic class \(S\) is said to be quasi-transitive if the subdigraph \(D[S]\) induced by \(S\) is quasi-transitive, that is, whenever \(x,y,z \in V(D[S])\) such that \((x,y), (y,z)\) are arcs in \(D[S]\), there exists either \((x,z)\) or \((z,x)\) in \(D[S]\).NEWLINENEWLINEIn this paper the authors give sufficient conditions for the existence of kernels by monochromatic directed paths in digraphs with quasi-transitive chromatic classes.
scientific article; zbMATH DE number 6206728