Discussiones Mathematicae Graph Theory 31(2) (2011) 283-292
doi: 10.7151/dmgt.1545

[BIBTex] [PDF] [PS]

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


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.


[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.

Received 26 November 2009
>Revised 18 December 2010
Accepted 19 December 2010