Monochromatic Cycles and Monochromatic Paths in arc-colored Digraphs

 Hortensia Galeana-Sánchez Guadalupe Gaytán-Gómez Instituto de Matemáticas Universidad Nacional Autónoma de México Ciudad Universitaria, México, D.F. 04510, México Roc'io Rojas-Monroy Facultad de Ciencias Universidad Autónoma del Estado de México Instituto Literario No. 100, Centro 50000, Toluca, Edo. de México, México

Abstract

We call the digraph D an m-colored digraph if the arcs of D are colored with m colors. A path (or a cycle) is called monochromatic if all of its arcs are colored alike. A cycle is called a quasi-monochromatic cycle if with at most one exception all of its arcs are colored alike. A subdigraph H in D is called rainbow if all its arcs have different colors. A set 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 ∈ N there is no monochromatic path 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. 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}. Notice that for any digraph D, ℭ (ℭ(D)) ≅ ℭ(D) and D has a kernel by monochromatic paths if and only if ℭ(D) has a kernel.

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 the subdigraph D[Ci] spanned by the arcs with colors in Ci is monochromatic. We show that if ℭ(D) does not contain neither rainbow triangles nor rainbow P3 involving colors of both C1 and C2, then D has a kernel by monochromatic paths.

This result is a wide extension of the original result by Sands, Sauer and Woodrow that asserts: Every 2-colored digraph has a kernel by monochromatic paths (since in this case there are no rainbow triangles in ℭ(D)).

Keywords: kernel, kernel by monochromatic paths, monochromatic cycles

2010 Mathematics Subject Classification: 05C20.

References

 [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 and V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67--76, doi: 10.1016/0012-365X(84)90131-6. [6] 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. [7] H. Galeana-Sánchez, On monochromatic paths and monochromatics cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103--112, doi: 10.1016/0012-365X(95)00036-V. [8] H. Galeana-Sánchez, Kernels in edge-coloured digraphs, Discrete Math. 184 (1998) 87--99, doi: 10.1016/S0012-365X(97)00162-3. [9] H. Galeana-Sánchez and J.J. Garcia-Ruvalcaba, Kernels in the closure of coloured digraphs, Discuss. Math. Graph Theory 20 (2000) 243--254 , doi: 10.7151/dmgt.1123. [10] 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. [11] S. Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. Theory (B) 45 (1988) 108--111, doi: 10.1016/0095-8956(88)90059-7. [12] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory (B) 33 (1982) 271--275, doi: 10.1016/0095-8956(82)90047-8. [13] 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.