Monochromatic cycles and monochromatic paths in arc-colored digraphs

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

Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 2, pp. 283-292

Résumé

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.

Détail

Keywords: kernel, kernel by monochromatic paths, monochromatic cycles