Graphs and Combinatorics DOI 10.1007/s00373-014-1499-9 ORIGINAL PAPER

Π-Kernels in Digraphs Hortensia Galeana-Sánchez · Juan José Montellano-Ballesteros

Received: 4 October 2013 / Revised: 11 September 2014 © Springer Japan 2014

Abstract Let D = (V (D), A(D)) be a digraph, D P(D) be the set of directed paths of D and let Π be a subset of D P(D). A subset S ⊆ V (D) will be called Π -independent if for any pair {x, y} ⊆ S, there is no x y-path nor yx-path in Π ; and will be called Π -absorbing if for every x ∈ V (D) \ S there is y ∈ S such that there is an x ypath in Π . A set S ⊆ V (D) will be called a Π -kernel if S is Π -independent and Π -absorbing. This concept generalize several “kernel notions” like kernel or kernel by monochromatic paths, among others. In this paper we present some sufficient conditions for the existence of Π -kernels. Keywords

Kernel · Kernel by monochromatic paths · Digraph

1 Introduction For general concepts we may refer the reader to [1,2]. Let D = (V (D), A(D)) be a digraph. In this work we only consider finite digraphs. A directed path P = (x0 , x1 , . . . , xn ) of D will be called an x0 xn -path. Given S1 , S2 ⊆ V (D), an S1 S2 path is an x y-path where x ∈ S1 and y ∈ S2 (if S1 = {x} we will write x S-path and Sx-path instead of {x}S-path and S{x}-path, respectively). A set K ⊆ V (D) is said to

Research partially supported by PAPIIT-México project IN101912 and by CONACYT 2013 project 219840. H. Galeana-Sánchez · J. J. Montellano-Ballesteros (B) Instituto de Matemáticas, Universidad Nacional Autónoma de México, Ciudad Universitaria, 04510 Mexico, D.F., Mexico e-mail: [email protected] H. Galeana-Sánchez e-mail: [email protected]

123

Graphs and Combinatorics

be a kernel if it is both independent (a vertex in K has no succesor in K ) and absorbing (a vertex not in K has a succesor in K ). This concept was first introduced in [11] by Von Neumann and Morgenstern in the context of Game Theory as a solution for cooperative n-player games. The concept of kernel arises naturally in applications such as Nim-type games, logic, and facility location, to name a few. For a comprehensive survey of this topic see for example [3,4]. A digraph D is said to be m-colored if its arcs are colored with m colors. Given an m-colored digraph D, a directed path is called monochromatic if all of its arcs are colored alike. A set N ⊆ V (D) is said to be a kernel by monochromatic paths if for every pair of different vertices in N there is no monochromatic directed path between them, and for every vertex x ∈ V (D) \ N there is a monochromatic x N -path. We can trace the origins of kernels by monochromatic paths to a problem due to Erdös and later to a theorem due to Sands, Sauer and Woodrow (see [12]). Observe that when m = 1, a kernel by monochromatic paths is a kernel by directed paths (see [2]). In [5] Galeana-Sánchez introduces formally the concept of kernel by monochromaic paths. The existence of kernels by monochromatic paths has been studied by several authors (see for example [6,8–10]). Let D = (V (D), A(D)) be a digraph and D P(D) be the set of directed paths of D. Given a subset Π of D P(D), a subset S ⊆ V (D) will be called Π -independent if for any pair {x, y} ⊆ S, there is no x y-path nor yx-path in Π ; and will be called Π -absorbing if for every x ∈ V (D) \ S there is a x S-path in Π . A set S ⊆ V (D) will be called a Π -kernel if S is Π -independent and Π -absorbing. Clearly, if Π is the set of arcs of D, a Π -kernel is a kernel of D, and if Π is the set of monochromatic paths of an m-colored digraph D, a Π -kernel is a kernel by monochromatic paths in D. In this paper we present some sufficient conditions for the existence of Π -kernels.

2 Notation and Previous Results Let D = (V (D), A(D)) be a digraph, D P(D) be the set of directed paths of D and let Π be a subset of D P(D). The elements of Π will be called Π -paths. Given x, y ∈ V (D) we will use (x →Π x) [respectively (x →Π y)] to denote the fact that there is an (respectively, no) x y-path in Π . In an analogous way, given S1 , S2 ⊆ V (D), we will use (S1 →Π S2 ) [respectively (S1 →Π S2 )] to denote the fact that there is an (respectively, no) S1 S2 -path in Π . We will said that D is Π -complete if for every pair x, y ∈ V (D), (x →Π y) or (y →Π x). The Π -closure of D is the digraph C Π (D) whose vertex-set is V (D) and the arc x y belongs to CΠ (D) if and only if (x →Π y).  A family P = [Πi ]i∈I of subsets of Π will be called a cover of Π if i∈I Πi = Π . Given a cover P = [Πi ]i∈I of Π , the P-closure of D is the arc-colored multidigraph C P (D) whose set of vertices is V (D), and the arc x y with “color” k ∈ I belongs to C P (D) if and only if (x →Πk y). A subdigraph H of C P (D) will be called P-rainbow if no two arcs of H have the same color. A subset Π1 ⊆ Π will be called Π -cyclically transitive if whenever there is a cyclic sequence (x0 , x1 , . . . , xn−1 , xn = x0 ) of vertices of D, such that for every i, 0 ≤ i < n, (xi →Π1 xi+1 ), then for some 0 ≤ j < n, (x j+1 →Π x j ). A subset

123

Graphs and Combinatorics

Π1 ⊆ H will be called transitive if whenever (x →Π1 y) and (y →Π1 z), then (x →Π1 z). Observe that if Π1 ⊆ Π is transitive, then Π1 is Π -cyclically transitive. A cover [Π1 , Π2 ] of Π will be called Π -cyclically transitive if Π1 and Π2 are both Π -cyclically transitive. A cover [Π1 , Π2 ] of Π will be called Π -transitive if Π1 and Π2 are both transitive. Definition 1 Let D be a digraph and Π ⊆ D P(D). Given Π1 ⊆ Π , a set S ⊆ V (D) will be called a Π -semikernel modulo Π1 whenever the two following conditions hold: (i) S is Π -independent. (ii) For each z ∈ V (D) \ S, if (S →Π1 z), then (z →Π S). The notion of Π -semikernel modulo Π1 comes from [12]. Lemma 1 Let D be a digraph, Π ⊆ D P(D) and let Π1 ⊆ Π be Π -cyclically transitive. (i) For each none empty set S ⊆ V (D) there is x0 ∈ S such that for each z ∈ S \{x0 }, if (x0 →Π1 z) then (z →Π x0 ). (ii) There is x0 ∈ V (D) such that {x0 } is a Π -semikernel modulo Π1 . Proof Let ∅ = S ⊆ V (D) and suppose there is no vertex x ∈ S such that for every z ∈ S \ {x}, if (x →Π1 z) then (z →Π x). Let y0 ∈ S. It follows that there is y1 ∈ S \ {y0 } such that (y0 →Π1 y1 ) and (y1 →Π y0 ). Thus there is y2 ∈ S \ {y1 } such that (y1 →Π1 y2 ) and (y2 →Π y1 ). Hence there is y3 ∈ S \ {y2 } such that (y2 →Π1 y3 ) and (y3 →Π y2 ). Following this procedure, we obtain an infinite sequence (y0 , y1 , . . .) of vertices of S ⊆ V (D) such that, for i ≥ 0, (yi →Π1 yi+1 ) and (yi+1 →Π yi ). Since S is a finite set, there exist j > i ≥ 0 such that yi = y j and therefore (yi , yi+1 , . . . y j−1 , y j = yi ) is a cyclic sequence of vertices of D such that for every k, i ≤ k < j, (yk →Π1 yk+1 ) and (yk+1 →Π yk ), which is not possible since Π1 is Π -cyclically transitive. Therefore (i) follows. For (ii) consider S = V (D) and the result follows.

Let Π1 ⊆ Π and SΠ1 (D) be the set of non-empty Π -semikernels modulo Π1 . Let DΠ1 = (V (DΠ1 ), A(DΠ1 )) be the digraph defined as follows: V (DΠ1 ) = SΠ1 (D) and for each pair {S1 , S2 } ⊆ SΠ1 (D), (S1 , S2 ) ∈ A(DΠ1 ) if and only if for every s1 ∈ S1 \ S2 there exists s2 ∈ S2 \ S1 such that (s1 →(Π\Π1 ) s2 ) and (s2 →Π s1 ). The definition of DΠ1 also comes from [12]. Let P = [Π1 , Π2 ] be a cover of Π . Observe that C P (D) is a 2-arc-colored multidigraph. A directed path P3 of C P (D) with the set of arcs {x y, yz, zw} will be called P-bad if x y and zw receive different colors, and the set of arcs of the subdigraph of CΠ (D) induced by {x, y, z, w} is a subset of {x y, yz, zw, zy, wy}. Let C3 be a directed triangle of C P (D) which is 2-arc-colored. Let {x y, yz, zx} be the set of arcs of C3 and, without loss of generality, suppose that the color of x y is different from the color of yz and zx. We will said that C3 is P-bad if the subdigraph of CΠ (D) induced by {x, y, z} has at least two asymmetric arcs, where x y (the arc of C3 with the “singular” color in C P (D)) is one of the asymmetric arcs.

123

Graphs and Combinatorics

Lemma 2 Let D be a digraph and Π ⊆ D P(D). Assume that Π has a Π -cyclically transitive cover P = [Π1 , Π2 ] such that there is neither a P-bad C3 nor a P-bad P3 + in C P (D). For every S ∈ SΠ1 (D) we have: if S is not a Π -kernel, then d D (S) ≥ 1. Π 1

Proof Let S ∈ SΠ1 (D) such that S is not a Π -kernel, and let X = {z ∈ V (D) : (z →Π S)}. Observe that since S ∈ SΠ1 (D), (S →Π1 X ). From Lemma 1 (i) there is x0 ∈ X such that for each z ∈ X \ {x0 }, if (x0 →Π1 z) then (z →Π x0 ). Let T = {z ∈ S : (z →Π x0 )}. Observe that by definition of T , for every z ∈ S \ T , (z →Π2 x0 ).    To prove the result we will show that T ∪{x0 } ∈ SΠ1 (D) and that S, T ∪{x0 }) is an   + arc in DΠ1 , and therefore d D (S) ≥ 1. To begin, we show that T ∪ {x } ∈ SΠ1 (D). 0 Π1 Since T ⊆ S ∈ SΠ1 (D), and by  of X and T , it follows that T ∪ {x0 } is  definition Π -independent. Let z ∈ V (D) \ T ∪ {x0 } and t ∈ T ∪ {x0 } such that (t →Π1 z). We will see that (z →Π T ∪ {x0 }). Since (t →Π1 z) it follows that z ∈ S and therefore z ∈ V (D) \S. If z ∈ X , since (t →Π1 z) we see that t = x0 and then (z →Π t). Let z ∈ V (D) \ S ∪ X . If (z →Π x0 ) we are done, so we can suppose (z →Π x0 ). Since z ∈ V (D) \ S ∪ X there is w ∈ S such that (z →Π w). We will see that w ∈ T . For the contrary, let us suppose w ∈ S \ T . Thus (w →Π2 x0 ). If t ∈ T it is not hard to see that {t, z, w, x0 } induces a P-bad P3 in C P (D), which is not possible. If t = x0 , since (x0 →Π w) and (z →Π x0 ) we see that {x0 , z, w} inducesa P-bad C3 in C P (D), which is a contradiction. Therefore w ∈ T and T ∪ {x0 } ∈ SΠ1 (D).   we conclude Finally, since for every z ∈ S \ T = S \ T ∪ {x0 } there is w ∈ T ∪ {x0 } such that (z →Π2 w), and (w →Π z) it follows that S, T ∪ {x0 }) is an arc in DΠ1 and the result follows.

3 Main Results Theorem 1 Let D be a digraph and Π ⊆ D P(D). If Π is Π -cyclically transitive, then D has a Π -kernel. Proof By Lemma 1 (ii) the set SΠ (D) of Π -semikernels modulo Π is not empty. Since D is finite, SΠ (D) is as well, and possesses a maximal element S under inclusion. Let T = {x ∈ V (D) \ S : (x → S)} and suppose T = ∅. Observe that since S ∈ SΠ (D) and by definition of T , (T →Π S) and (S →Π T ). By Lemma 1 (i) there is x0 ∈ T such that for each z ∈ T \ {x0 }, if (x0 →Π z) then (z →Π x0 ). Let S ∗ = S ∪ {x0 }. Clearly S ∗ is independent by Π -paths. Let z ∈ V (D) \ S ∗ and suppose (t →Π z), with t ∈ S ∗ . If z ∈ V (D) \ (T ∪ S) then (z →Π S) and thus (z →Π S ∗ ). If z ∈ T \ {x0 }, since (t →Π z) it follows that t = x0 and hence (z →Π x0 ), which implies (z →Π S ∗ ). Therefore S ∗ ∈ SΠ (D) and S is a

proper subset of S ∗ which is a contradiction. Thus T = ∅ and S is a Π -kernel. As a corollary of Theorem 1 we have Corollary 1 Let D be a digraph and Π ⊆ D P(D). If every cycle in CΠ (D) has a symmetric arc, then D has a Π -kernel.

123

Graphs and Combinatorics

Proof Suppose D has no Π -kernel. Thus, by Theorem 1, Π is not Π -cyclically transitive and there is a cyclic sequence C = (x0 , x1 , . . . , xn−1 , xn = x0 ) such that for every i, 0 ≤ i < n, (xi →Π xi+1 ) and (xi+1 →Π xi ). Clearly V (C) induces a cycle

in CΠ (D) with no symmetric arcs and the result follows. Theorem 2 Let D be a digraph and Π ⊆ D P(D) be such that D is Π -complete. Moreover, suppose that there is a cover P = [Πi ]i∈I of Π such that for every i ∈ I , Πi is transitive. If for every P-rainbow C3 in C P (D), the subgraph induced by its vertices in CΠ (D) has at least two symmetric arcs, then D has a Π -kernel. Proof First we will see that Π is Π -cyclically transitive. For the contrary suppose there is a cyclic sequence of vertices C = (x0 , x1 , . . . , xn−1 , xn = x0 ) of D, of minimum order, such that for every i, 0 ≤ i < n there is a xi xi+1 -path Txi xi+1 in Π and for every j, 0 ≤ j < n, (x j+1 →Π x j ). If every Txi xi+1 belongs to a single Πk ∈ P, since Πk is transitive it follows that (x j+1 →Πk x j ) for every j, 0 ≤ j < n, which is not possible. Thus there are j, k ∈ I, with j = k, such that, without loss of generality, Tx0 x1 ∈ Πk and Tx1 x2 ∈ Π j . Since D is Π -complete, either (x0 →Π x2 ) or (x2 →Π x0 ). Let us suppose (x2 →Π x0 ) and let Tx2 x0 be an x2 x0 -path in Π . If Tx2 x0 ∈ Πq , with q = k and q = j, it follows that (x0 , x1 , x2 , x0 ) is a P-rainbow C3 in C P (D) and therefore, by hypothesis, the induced subgraph by {x0 , x1 , x2 } of CΠ (D) has at least two symmetric arcs. Thus, either x1 x0 or x2 x1 is an arc of CΠ (D) which implies that either (x1 →Π x0 ) or (x2 →Π x1 ) which is not possible. Thus, either Tx2 x0 ∈ Π j or Tx2 x0 ∈ Πk . If Tx2 x0 ∈ Π j , since Tx1 x2 ∈ Π j and Π j is transitive, we see that (x1 →Π j x0 ), which is not possible. In the same way, if Tx2 x0 ∈ Πk we see that (x2 →Πk x1 ) which is a contradiction. Therefore (x2 →Π x0 ) and (x0 →Π x2 ). Hence (x0 , x2 , . . . , xn−1 , xn = x0 ) is a cyclic sequence of vertices of D, such that (x0 →Π x2 ) and for every i, 2 ≤ i < n, (xi →Π xi+1 ). Since C is of minimum order, it follows that (x2 →Π x0 ) which is a contradiction. Thus Π is Π -cyclically transitive and by Theorem 1 the result follows.

Theorem 3 Let D be a digraph and Π ⊆ D P(D). If there is a Π -cyclically transitive cover P = [Π1 , Π2 ] such that there is no P-bad C3 nor P-bad P3 in C P (D), then D has a Π -kernel. Proof To prove the result we will show that if [Π1 , Π2 ] is a Π -cyclically transitive cover, then DΠ1 is an acyclic digraph. From this it follows that there is S ∈ V (DΠ1 ) + (S) = 0 which, by Lemma 2, implies that S is a Π -kernel of D. such that d D Π1 Suppose to the contrary that [Π1 , Π2 ] is a Π -cyclically transitive cover and there is a cycle C = (S0 , S1 , . . . , Sn−1 , Sn = S0 ) in DΠ1 (with n ≥ 2). Note that Si = S j whenever i = j as C is a cycle. Claim 1. If there is i 0 ∈ {0, 1, . . . , n − 1} such that for some z ∈ Si0 and some w ∈ Si0 +1 , (z →Π w), then there is j0 ∈ {0, 1, . . . , n − 1} \ {i 0 } such that w ∈ S j0 \ S j0 +1 . Suppose, without loss of generality, that i 0 = 0. Observe that w ∈ S0 = Sn since S0 is independent by Π -paths.  Since w ∈ S1 and w ∈ Sn , there is j0 = max {i ∈

{0, 1, . . . , n − 1} : w ∈ Si } . Therefore w ∈ S j0 \ S j0 +1 . There is i 0 ∈ {0, 1, . . . , n − 1} such that Si0 \ Si0 +1 = ∅. Let x0 ∈Si0 \ Si0 +1 . Since (Si0 , Si0 +1 ) ∈ A(DΠ1 ), we see that there is x1 ∈ Si0 +1 \ Si0 such that x0 →(Π\Π1 ) x1

123

Graphs and Combinatorics

and (x1 →Π Si0 ). From Claim 1, there is i 1 ∈ {0, 1, . . . , n − 1} \ {i 0 } such that x1 ∈ Si1 \ Si1 +1 . Thus,  since (Si1 , Si1 +1 ) ∈ A(DΠ1 ), there is x2 ∈ Si1 +1 \ Si1 such that x1 →(Π\Π1 ) x2 and (x2 →Π Si1 ). From Claim 1, there is i 2 ∈ {0, 1, . . . , n − 1} \ {i 1 } such that x2 ∈ Si2 \ Si2 +1 . Following this procedure, since Π \ Π1 ⊆ Π2 , we obtain an infinite sequence (x0 , x1 , . . .) of vertices of V (D) such that, for i ≥ 0, (xi →Π2 xi+1 ) and (xi+1 →Π x1 ). Since C is finite there is a cyclic sequence (x0 , x1 , x2 , . . . , xm−1 , xm = x0 ) of vertices of D such that, for each 0 ≤ i ≤ m − 1, (xi →Π2 xi+1 ) and (xi+1 →Π x1 ), which is a contradiction since [Π1 , Π2 ] is a Π -cyclically transitive cover. Corollary 2 Let D be a digraph and Π ⊆ D P(D). If there is a Π -transitive cover P = [Π1 , Π2 ] of Π , then D has a Π -kernel. Proof Suppose there is a Π -transitive cover P = [Π1 , Π2 ]. It follows that P = [Π1 , Π2 ] is a Π -cyclically transitive cover. Let A = {x y, yz, zw} be a set of arcs in C P (D) such that x y and zw receive different colors. Thus, we can suppose, without loss of generality, that yz receives the same color as x y. Therefore, by definition, there is an x y-path and a yz-path in the same part Πi of P. Since Πi is transitive, there is a x z-path in Πi and thus the arc x z belongs to C P (D). Hence A does not induces a P-bad P3 in C P (D). In an analogous way, if A = {x y, yz, zx} is a set of arcs of C P (D), where x y receives a different color from yz and zx, the arc arc yx belongs to C P (D) and then A does not induces a P-bad C3 in C P (D). From here and by Theorem 3, the result follows.

4 Some Consequences As a direct consequence of Theorem 1 and Corollary 2 we have the following results, due to Berge (see [2]). Theorem 4 Let D be a digraph. (i) D has a kernel by directed paths. (ii) If D is the union of two transitive digraphs D1 and D2 , then D has a kernel. Proof (i) Let Π = D P(D). It is not hard to see that Π is Π -cyclically transitive, and by Theorem 1 the result follows. (ii) Let Π ⊆ D P(D) be the set of arcs of D, and P = [Π1 , Π2 ] be a cover of Π where Π1 is the set of arcs of D1 and Π2 the set of arcs of D2 . Since D1 and D2 are transitive digraphs, it is not hard to see that P is a Π -transitive cover of Π , and by Corollary 2 the result follows.

As a direct implication of Corollary 2 we have the following theorem due to Sands, Sauer and Woodrow [12]: Theorem 5 Let D = (V (D), A(D)) be a digraph and  : A(D) → {1, 2} be an arc-coloring of D. Then D has a kernel by monochromatic paths.

123

Graphs and Combinatorics

Proof Let Π ⊆ D P(D) be the set of monochromatic paths of D, and Πi be the set of monochromatic paths of D with color i, with i ∈ {1, 2}. It is not hard to see that [Π1 , Π2 ] is a Π -transitive cover and by Corollary 2 the result follows. Let D = (V (D), A(D)) be an m-colored digraph. If C is a set of colors, D[C] will denote the subdigraph of D spanned by the arcs with colors in C. The closure of D is the m-colored multidigraph C(D) whose set of vertices is V (D), and an arc x y with color j belongs to C(D) if and only if there is a monochromatic x y-path in D with color j. A subdigraph H of an m-colored digraph D will be called rainbow if no two arcs of H received the same color. As an implication of Theorem 3 we have the following theorem due to GaleanaSánchez, Gaytán-Gómez and Rojas-Monroy [7]: Theorem 6 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 D[Ci ] is monochromatic. Suppose, moreover, that C(D) contains neither rainbow directed triangles nor rainbow P3 involving colors of both C1 and C2 . Then D has a kernel by monochromatic paths. Proof Let Π ⊆ D P(D) be the set of monochromatic paths of D. Let Π1 be the set of monochromatic paths of D with a color in C1 and Π2 be the set of monochromatic paths vertices of D with a color in C2 . Let (x0 , x1 , . . . , xn−1 , xn = x0 ) be a cyclic sequence of n A(Ti ) of D, such that for every i, 0 ≤ i < n there is a xi xi+1 -path Ti in Π1 . Thus i=0 induces a closed walk W in D[C1 ]. Let E 1 , . . . , Er be a cover of W consisting of directed cycles. Since every cycle in D[C1 ] is monochromatic, every arc (z, w) in W of color c belongs to a monochromatic directed cycle E j (of color c) and therefore there is a monochromatic wz-path of color c. Thus, if T0 = (x0 = y0 , y1 , . . . , y p = x1 ) is a monochromatic x0 x1 -path of color c ∈ C1 , there is a walk from x1 to x0 of color c and therefore there is a monochromatic x1 x0 -path of color c ∈ C1 . From here it follows that Π1 is Π -cyclically transitive. In the same way we see that Π2 is Π -cyclically transitive and therefore P = [Π1 , Π2 ] is a Π -cyclically transitive cover. Let C3 be a directed triangle of CΠ (D) with set of arcs {x y, yz, zx} such that the color of x y is different from the color of yz and zx. Without loss of generality, suppose that there is a x y-path in Π1 with color c1 ∈ C1 , a yz-path in Π2 with color c2 ∈ C2 and a zx-path in Π2 with color d2 ∈ C2 . Since c1 ∈ C1 and d2 ∈ C2 it follows that c1 = d2 and since there is no rainbow directed triangles in C(D) involving colors of C1 and C2 , we see that d2 = c2 . Hence there is a monochromatic walk of color d2 from y to x (and therefore there is a yx-path in Π and the arc yx belongs to CΠ (D)). Thus, {x, y, z} does not induce a P-bad C3 in CΠ (D). In the same way we see that

there is no P-bad P3 in CΠ (D), and by Theorem 3 the result follows. Given a m-colored tournament T = (V, A), the associated multitournament T = (T0 , . . . , Tm−1 ) is defined as follows. For each i, the digraph Ti = (V, Ai ) is such that for a pair x, y ∈ V , x y ∈ Ai if and only if there is a monochromatic x y-path of color i. Observe that every Ti is transitive and T is complete (for every pair of vertices x, y, there is a color i such that x y or yx (or both) is an arc of Ti ). Let U = {U0 , . . . , Um−1 } be obtained from T by deleting arcs from the Ti s. Such a multitournament is called minimal if no arc may be removed from it without destroying either the completeness of U, or the transitivity of the Ui s, or both.

123

Graphs and Combinatorics

As an implication of Theorem 2 we have the following theorem due to Hahn, Ille and Woodrow [8]: Theorem 7 Let T = (V, A) be an m-coloured tournament and let a minimal multitournament U = {U0 , . . . , Um−1 } be obtained from the associated   multitournament. m−1 A(Ui ) is a If U is without rainbow directed triangles then the digraph V, i=0 total order whose maximum is an absorbing vertex in T . Proof Let T = (V, A) be an m-coloured tournament and suppose a minimal multitournament U = {U0 , . . . , Um−1 } is without rainbow directed triangles. Let Π be the set of arcs of U and let P = [Πi ]1≤i≤m be a cover of Π such that for every i, 1 ≤ i ≤ m, Πi = A(Ui ). By hypothesis U is complete and therefore is Π -complete; and for each i, 1 ≤ i ≤ m, Πi is transitive. Since there are no rainbow directed triangles in U, we see that there is no rainbow triangle in C P (U), and therefore, by Theorem 2, U has a Π -kernel, which has to be a singular vertex x, since U is complete. Finally, since every monochromatic path in U is a monochromatic path in T , it follows that there is an absorving set.

Acknowledgments The authors would like to express their gratitude to the referees for their insightful comments and remarks, which helped to improved the quality of this paper.

References 1. Bang-Jensen, J., Gutin, G.: Digraphs: theory algorithms and applications. Springer, London (2000) 2. Berge, C.: Graphs. North-Holland, Amsterdam (1989) 3. Boros, E., Gurvich, V.: Perfect graphs, kernels and cores of cooperative games. Discret. Math. 306(19– 20), 2336–2354 (2006) 4. Fraenkel, A.S.: Combinatorial games: selected bibliography with a succinct gourmet introduction. Electron. J. Comb. 14(DS2), 1–88 (2009) 5. Galeana-Sánchez, H.: On monochromatic paths and monochromatic cycles in edge coloured tournaments. Discret. Math. 156, 103–112 (1996) 6. Galeana-Sánchez, H.: Kernels in edge coloured digraphs. Discret. Math. 184, 87–99 (1998) 7. Galeana-Sánchez, H., Gaytán-Gómez, G., Rojas-Monroy, R.: Monochromatic cycles and monochromatic paths in arc-colored digraphs. Discuss. Math. Graph Theory 31(2), 283–292 (2011) 8. Hahna, G., Ille, P., Woodrow, R.E.: Absorving sets in arc-coloured tournaments. Discret. Math. 283, 93–99 (2004) 9. Linek, V., Sands, B.: A note on paths in edge-coloured tournaments. Ars Comb. 44, 225–228 (1996) 10. Minggang, S.: On monochromatic paths in m-coloured tournaments. J. Comb. Theory Ser. B 45, 108–111 (1988) 11. Neumann, J.V., Morgenstern, O.: Theory of games and economic behavior. Princeton University Press, Princeton (1944) 12. Sands, B., Sauer, N., Woodrow, R.: On monochromatic paths in edge coloured digraphs. J. Comb. Theory Ser. B 33, 271–275 (1982)

123