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: for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, and 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 γ = (u0, u1, . . . , un, u0) such that for every i ∈ {0, 1, . . . , n}: there is a uiui+1-monochromatic path, and there is no ui+1ui-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 = C1 ∪ C2 of the set of colors of D such that: D[Ĉi] (the subdigraph spanned by the arcs with colors in Ci) contains no γ-cycles for i ∈ {1, 2}; If ℭ (D) contains a rainbow C3 = (x0, z, w, x0) involving colors of C1 and C2, then (x0, w) ∈ A(ℭ (D)) or (z, x0) ∈ A(ℭ (D)); If ℭ (D) contains a rainbow P3 = (u, z, w, x0) involving colors of C1 and C2, then at least one of the following pairs of vertices is an arc in ℭ (D): (u, w), (w, u), (x0, u), (u, x0), (x0, w), (z, u), (z, x0). 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.
@article{bwmeta1.element.doi-10_7151_dmgt_1848,
author = {Hortensia Galeana-S\'anchez and Guadalupe Gayt\'an-G\'omez and Roc\'\i o Rojas-Monroy},
title = {$\gamma$-Cycles In Arc-Colored Digraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {103-116},
zbl = {1329.05131},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1848}
}
Hortensia Galeana-Sánchez; Guadalupe Gaytán-Gómez; Rocío Rojas-Monroy. γ-Cycles In Arc-Colored Digraphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 103-116. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1848/
[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[Crossref]
[3] P. Duchet, Classical perfect graphs: An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67–96. | Zbl 0558.05038
[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[Crossref] | Zbl 0456.05032
[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[Crossref]
[6] H. Galeana-Sánchez, Kernels in edge-coloured digraphs, Discrete Math. 184 (1998) 87–99. doi:10.1016/S0012-365X(97)00162-3[Crossref][WoS]
[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[Crossref] | Zbl 0990.05059
[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[Crossref][WoS] | Zbl 1234.05112
[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[Crossref] | Zbl 0529.05024
[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[Crossref] | Zbl 0593.05034
[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[Crossref] | Zbl 1042.05039
[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[Crossref] | Zbl 1049.05042
[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[Crossref] | Zbl 1075.05033
[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[Crossref] | Zbl 1156.05022
[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. | Zbl 1210.05054
[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[Crossref] | Zbl 1193.05078
[17] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944). | Zbl 0063.05930
[18] M. Richardson, Solutions of irreflexive relations, Ann. of Math. 58 (1953) 573–590. doi:10.2307/1969755[Crossref] | Zbl 0053.02902
[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[Crossref] | Zbl 0053.02903
[20] R. Rojas-Monroy and J.I. Villarreal-Valdés, Kernels in infinite diraphs, AKCE Int. J. Graphs Comb. 7 (2010) 103–111. | Zbl 1223.05101
[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[Crossref] | Zbl 0654.05033
[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[Crossref] | Zbl 0488.05036
[23] I. Włoch, On imp-sets and kernels by monochromatic paths of the duplication, Ars Combin. 83 (2007) 93–99. | Zbl 1174.05114
[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[Crossref][WoS] | Zbl 1152.05033