Article ID Journal Published Year Pages File Type
419576 Discrete Applied Mathematics 2010 6 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,