k-colored kernels in semicomplete multipartite digraphs

arXiv1202.4017MaRDI QIDQ6231098FDOQ6231098

Authors: Hortensia Galeana-Sánchez, Bernardo Llano, Juan José Montellano-Ballesteros 

Publication date: 17 February 2012

Abstract: An $m$-colored digraph $D$ has $k$-colored kernel if there exists a subset $K$ of its vertices such that for every vertex $votinK$ there exists an at most $k$-colored directed path from $v$ to a vertex of $K$ and for every $\mathrm{\%}u,vinK$ there does not exist an at most $k$-colored directed path between them. In this paper we prove that an $m$-colored semicomplete $r$-partite digraph $D$ has a $k$-colored kernel provided that $rgeq3$ and {enumerate} [(i)] $kgeq4,$ [(ii)] $k=3$ and every $overrightarrow{C}_4$ contained in $D$ is at most 2-colored and, either every $overrightarrow{C}_5$ contained in $D$ is at most 3-colored or every $overrightarrow{C}_{3}uparrowoverrightarrow{C}_3$ contained in $D$ is at most 2-colored, [(iii)] $k=2$ and every $overrightarrow{C}_3$ and $overrightarrowC{\mathrm{\%}}_4$ contained in $D$ is monochromatic. {enumerate} If $D$ is an $m$-colored semicomplete bipartite digraph and $k=2$ (resp. $k=3$) and every $overrightarrow{C}_{4}upuparrowsoverrightarrow{C}_4$ contained in $D$ is at most 2-colored (resp. 3-colored), then $D$ has a $\mathrm{\%}2$-colored (resp. 3-colored) kernel. Using these and previous results, we obtain conditions for the existence of $k$-colored kernels in $m$-colored semicomplete $r$-partite digraphs for every $kgeq2$ and $rgeq2$.

This page was built for publication: $k$-colored kernels in semicomplete multipartite digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6231098)