Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419576 | Discrete Applied Mathematics | 2010 | 6 Pages |
Abstract
A digraph DD is a union of quasi-transitive digraphs if its arcs can be partitioned into sets A1A1 and A2A2 such that the induced subdigraph D[Ai](i=1,2) is quasi-transitive. Let DD be an mm-colored asymmetric union of quasi-transitive digraphs such that every chromatic class is completely included in D[Ai]D[Ai] for some i=1,2i=1,2 and is quasi-transitive. We show that if DD does not contain 3-colored triangles (directed cycles and transitive subtournaments of order 3), then DD has a kernel by monochromatic directed paths.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hortensia Galeana-Sánchez, Bernardo Llano, Juan José Montellano-Ballesteros,