$ \gamma $-Cycles In Arc-Colored Digraphs

Galeana-Sánchez, Hortensia ; Gaytán-Gómez, Guadalupe ; Rojas-Monroy, Rocío

Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 103-116.

Résumé

We call a digraph D an m-colored digraph if the arcs of D are colored with m colors. A directed path (or a directed cycle) is called monochromatic if all of its arcs are colored alike. A subdigraph H in D is called rainbow if all of its arcs have different colors. A set N ⊆ V (D) is said to be a kernel by monochromatic paths of D if it satisfies the two following conditions: (i) for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, and (ii) for every vertex x ∈ V (D) − N there is a vertex y ∈ N such that there is an xy-monochromatic path in D. A γ-cycle in D is a sequence of different vertices γ = (u_0, u_1, . . ., u_n, u_0) such that for every i ∈0, 1, . . ., n: (i) there is a u_i u_i+1-monochromatic path, and (ii) there is no u_i+1u_i-monochromatic path. The addition over the indices of the vertices of γ is taken modulo (n + 1). If D is an m-colored digraph, then the closure of D, denoted by ℭ(D), is the m-colored multidigraph defined as follows: V (ℭ (D)) = V (D), A( ℭ (D)) = A(D) ∪{ (u, v) with color i | there exists a uv-monochromatic path colored i contained in D }. In this work, we prove the following result. Let D be a finite m-colored digraph which satisfies that there is a partition C = C_1 ∪ C_2 of the set of colors of D such that: (1) D[ Ĉ_i ] (the subdigraph spanned by the arcs with colors in C_i) contains no γ-cycles for i ∈1, 2; (2) If ℭ(D) contains a rainbow C_3 = (x_0, z, w, x_0) involving colors of C_1 and C_2, then (x_0, w) ∈ A(ℭ (D)) or (z, x_0) ∈ A( ℭ (D)); (3) If ℭ(D) contains a rainbow P_3 = (u, z, w, x_0) involving colors of C_1 and C_2, then at least one of the following pairs of vertices is an arc in ℭ (D): (u, w), (w, u), (x_0, u), (u, x_0), (x_0, w), (z, u), (z, x_0). Then D has a kernel by monochromatic paths. This theorem can be applied to all those digraphs that contain no γ-cycles. Generalizations of many previous results are obtained as a direct consequence of this theorem.

Détail

Keywords: digraph, kernel, kernel by monochromatic paths, γ-cycle

Bibliographie

[1] C. Berge, Graphs (North-Holland, Amsterdam, 1985).

[2] P. Duchet, Graphes Noyau-Parfaits, Ann. Discrete Math. 9 (1980) 93–101. doi:10.1016/S0167-5060(08)70041-4

[3] P. Duchet, Classical perfect graphs: An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67–96.

[4] P. Duchet and H. Meyniel, A note on kernel-critical graphs, Discrete Math. 33 (1981) 103–105. doi:10.1016/0012-365X(81)90264-8

[5] H. Galeana-Sánchez, On monochromatic paths and monochromatics cycles in edge colored tournaments, Discrete Math. 156 (1996) 103–112. doi:10.1016/0012-365X(95)00036-V

[6] H. Galeana-Sánchez, Kernels in edge-coloured digraphs, Discrete Math. 184 (1998) 87–99. doi:10.1016/S0012-365X(97)00162-3

[7] H. Galeana-Sánchez and J.J. García-Ruvalcaba, Kernels in the closure of coloured digraphs, Discuss. Math. Graph Theory 20 (2000) 243–254. doi:10.7151/dmgt.1123

[8] H. Galeana-Sánchez, G. Gaytán-Gómez and R. Rojas-Monroy, Monochromatic cycles and monochromatic paths in arc-colored digraphs, Discuss. Math. Graph Theory 31 (2011) 283–292. doi:10.7151/dmgt.1545

[9] H. Galeana-Sánchez and V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67–76. doi:10.1016/0012-365X(84)90131-6

[10] H. Galeana-Sánchez and V. Neumann-Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986) 257–265. doi:10.1016/0012-365X(86)90172-X

[11] H. Galeana-Sánchez and R. Rojas-Monroy, A counterexample to a conjecture on edge-coloured tournaments, Discrete Math. 282 (2004) 275–276. doi:10.1016/j.disc.2003.11.015

[12] H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and monochromatic 4- cycles in edge coloured bipartite tournaments, Discrete Math. 285 (2004) 313–318. doi:10.1016/j.disc.2004.03.005

[13] H. Galeana-Sánchez and R. Rojas-Monroy, Monochromatic paths and at most 2- coloured arc sets in edge-coloured tournaments, Graphs Combin. 21 (2005) 307–317. doi:10.1007/s00373-005-0618-z

[14] H. Galeana-Sánchez and R. Rojas-Monroy, Monochromatic paths and quasi-monochromatic cycles in edge-coloured bipartite tournaments, Discuss. Math. Graph Theory 28 (2008) 285–306. doi:10.7151/dmgt.1406

[15] H. Galeana-Sánchez and R. Rojas-Monroy, Independent domination by monochromatic paths in arc coloured bipartite tournaments, AKCE Int. J. Graphs Comb. 6 (2009) 267–285.

[16] H. Galeana-Sánchez, R. Rojas-Monroy and B. Zavala, Monochromatic paths and monochromatic sets of arcs in 3- quasitransitive digraphs, Discuss. Math. Graph Theory 29 (2009) 337–347. doi:10.7151/dmgt.1450

[17] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944).

[18] M. Richardson, Solutions of irreflexive relations, Ann. of Math. 58 (1953) 573–590. doi:10.2307/1969755

[19] M. Richardson, Extension theorems for solutions of irreflexive relations, Proc. Natl. Acad. Sci. USA 39 (1953) 649–655. doi:10.1073/pnas.39.7.649

[20] R. Rojas-Monroy and J.I. Villarreal-Valdés, Kernels in infinite diraphs, AKCE Int. J. Graphs Comb. 7 (2010) 103–111.

[21] Shen Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. Theory Ser. B 45 (1988) 108–111. doi:10.1016/0095-8956(88)90059-7

[22] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths edge-coloured digraphs, J. Combin. Theory Ser. B 33 (1982) 271–275. doi:10.1016/0095-8956(82)90047-8

[23] I. Włoch, On imp-sets and kernels by monochromatic paths of the duplication, Ars Combin. 83 (2007) 93–99.

[24] I. Włoch, On kernels by monochromatic paths in the corona of digraphs, Cent. Eur. J. Math. 6 (2008) 537–542. doi:10.2478/s11533-008-0044-6