2012/02/17 by Hortensia Galeana-Sánchez, Hortensia Galeana‐Sánchez, Galeana-Sánchez, Hortensia +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1202.4017
arxiv created 2012/02/17 · openalex publication_date 2012/02/17 · arxiv updated 2012/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
An m-colored digraph D has k-colored kernel if there exists a subset K of its vertices such that for every vertex v∉ K there exists an at most k-colored directed path from v to a vertex of K and for every % u,v∈ 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≥ 3 and enumerate [(i)] k≥ 4, [(ii)] k=3 and every \overrightarrowC4 contained in D is at most 2-colored and, either every \overrightarrowC5 contained in D is at most 3-colored or every \overrightarrowC3\uparrow \overrightarrowC3 contained in D is at most 2-colored, [(iii)] k=2 and every \overrightarrowC3 and \overrightarrowC%4 contained in D is monochromatic. enumerate If D is an m-colored semicomplete bipartite digraph and k=2 (resp. k=3 ) and every \overrightarrowC4\upuparrows \overrightarrowC4 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≥ 2 and r≥ 2.