Monochromatic cycles and monochromatic paths in arc-colored digraphs

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

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 283-292
  • ISSN: 2083-5892

Abstract

top
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 = C₁ ∪ C₂ of the set of colors of D such that every cycle in the subdigraph D [ C i ] spanned by the arcs with colors in C i is monochromatic. We show that if ℭ(D) does not contain neither rainbow triangles nor rainbow P₃ involving colors of both C₁ and C₂, 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)).

How to cite

top

Hortensia Galeana-Sánchez, Guadalupe Gaytán-Gómez, and Rocío Rojas-Monroy. "Monochromatic cycles and monochromatic paths in arc-colored digraphs." Discussiones Mathematicae Graph Theory 31.2 (2011): 283-292. <http://eudml.org/doc/270813>.

@article{HortensiaGaleana2011,
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 = C₁ ∪ C₂ of the set of colors of D such that every cycle in the subdigraph $D[C_i]$ spanned by the arcs with colors in $C_i$ is monochromatic. We show that if ℭ(D) does not contain neither rainbow triangles nor rainbow P₃ involving colors of both C₁ and C₂, 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)).},
author = {Hortensia Galeana-Sánchez, Guadalupe Gaytán-Gómez, Rocío Rojas-Monroy},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; kernel by monochromatic paths; monochromatic cycles; monochromatic paths},
language = {eng},
number = {2},
pages = {283-292},
title = {Monochromatic cycles and monochromatic paths in arc-colored digraphs},
url = {http://eudml.org/doc/270813},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - Guadalupe Gaytán-Gómez
AU - Rocío Rojas-Monroy
TI - Monochromatic cycles and monochromatic paths in arc-colored digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 283
EP - 292
AB - 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 = C₁ ∪ C₂ of the set of colors of D such that every cycle in the subdigraph $D[C_i]$ spanned by the arcs with colors in $C_i$ is monochromatic. We show that if ℭ(D) does not contain neither rainbow triangles nor rainbow P₃ involving colors of both C₁ and C₂, 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)).
LA - eng
KW - kernel; kernel by monochromatic paths; monochromatic cycles; monochromatic paths
UR - http://eudml.org/doc/270813
ER -

References

top
  1. [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985). 
  2. [2] P. Duchet, Graphes Noyau - Parfaits, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4. 
  3. [3] P. Duchet, Classical Perfect Graphs, An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67-96. Zbl0558.05038
  4. [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. Zbl0456.05032
  5. [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. Zbl0529.05024
  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. Zbl0593.05034
  7. [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. [8] H. Galeana-Sánchez, Kernels in edge-coloured digraphs, Discrete Math. 184 (1998) 87-99, doi: 10.1016/S0012-365X(97)00162-3. Zbl0958.05061
  9. [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. Zbl0990.05059
  10. [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. Zbl1042.05039
  11. [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. Zbl0654.05033
  12. [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. Zbl0488.05036
  13. [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. Zbl1152.05033
  14. [14] I. Włoch, On imp-sets and kernels by monochromatic paths in duplication, Ars Combin. 83 (2007) 93-99. Zbl1174.05114

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.