کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648052 | 1342391 | 2011 | 8 صفحه PDF | دانلود رایگان |
We call the digraph DD an kk-colored digraph if the arcs of DD are colored with kk colors. A subdigraph HH of DD is called monochromatic if all of its arcs are colored alike. A set N⊆V(D)N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v∈Nu,v∈N, there is no monochromatic directed path between them, and (ii) for every vertex x∈(V(D)∖N)x∈(V(D)∖N), there is a vertex y∈Ny∈N such that there is an xyxy-monochromatic directed path. In this paper, we prove that if DD is an kk-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3,43,4 or 55 is monochromatic, then DD has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural number llsuch that if a digraph DDis kk-colored so that every directed cycle of length at most llis monochromatic, then DDhas a kernel by monochromatic paths?
Journal: Discrete Mathematics - Volume 311, Issue 13, 6 July 2011, Pages 1111–1118