ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2019: 0.600
Rejection Rate (2018-2019): c. 84%
Discussiones Mathematicae Graph Theory 31(2) (2011)
Let D be a finite m-colored digraph. Suppose that there is a partition
C = C1∪C2 of the set of colors of D such that every cycle in the
subdigraph D[Ci] spanned by the arcs with colors in Ci is monochromatic.
We show that if ℭ(D) does not contain neither rainbow triangles
nor rainbow P3 involving colors of both C1 and C2, then D has a
kernel by monochromatic paths.
This result is a wide extension of the original result by Sands, Sauer and
Woodrow that asserts: Every 2-colored digraph has a kernel by monochromatic
paths (since in this case there are no rainbow triangles in ℭ(D)).
Keywords: kernel, kernel by monochromatic paths, monochromatic cycles
2010 Mathematics Subject Classification: 05C20.
Received 26 November 2009>Revised 18 December 2010
Accepted 19 December 2010