$k$-colored kernels in semicomplete multipartite digraphs

Details $k$-colored kernels in semicomplete multipartite digraphs $k$-colored kernels in semicomplete multipartite digraphs

2012-02-17

arxiv.org/abs/1202.4017v1

Mathematics

Combinatorics

Scientific paper

An $m$-colored digraph $D$ has $k$-colored kernel if there exists a subset $K $ of its vertices such that for every vertex $v\notin K$ there exists an at most $k$-colored directed path from $v$ to a vertex of $K$ and for every $% u,v\in K$ 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 $r\geq 3$ and {enumerate} [(i)] $k\geq 4,$ [(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}\uparrow \overrightarrow{C}_{3}$ contained in $D$ is at most 2-colored, [(iii)] $k=2$ and every $\overrightarrow{C}_{3}$ and $\overrightarrow{C}%_{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}\upuparrows \overrightarrow{C}_{4}$ contained in $D$ is at most 2-colored (resp. 3-colored), then $D$ has a $% 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 $k\geq 2$ and $r\geq 2$.

Affiliated with

Also associated with

No associations

Rating

$k$-colored kernels in semicomplete multipartite digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with $k$-colored kernels in semicomplete multipartite digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $k$-colored kernels in semicomplete multipartite digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32243