Kernels by monochromatic directed paths in \(m\)-colored digraphs with quasi-transitive chromatic classes.
type: Item
instance of: scholarly article
zbMATH Open document ID: 1289.05189
author: Hortensia Galeana-Sánchez
author: Bernardo Llano
author: Juan José Montellano-Ballesteros
publication date: 2013-09-09T00:00:00Z
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6206728
zbMATH Keywords: \(m\)-colored quasi-transitive digraph
zbMATH Keywords: kernel by monochromatic paths
zbMATH Keywords: quasi-transitive chromatic class
MaRDI profile type: MaRDI publication profile
title: Kernels by monochromatic directed paths in \(m\)-colored digraphs with quasi-transitive chromatic classes.
published in: Ars Combinatoria
review text: 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.
reviewed by: Josef Lauri
description: scientific article; zbMATH DE number 6206728