Kernels by Monochromatic Paths and Color-Perfect Digraphs

Hortensia Galeana-Śanchez; Rocío Sánchez-López

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 309-321
  • ISSN: 2083-5892

Abstract

top
For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph CC(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and CC(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.

How to cite

top

Hortensia Galeana-Śanchez, and Rocío Sánchez-López. "Kernels by Monochromatic Paths and Color-Perfect Digraphs." Discussiones Mathematicae Graph Theory 36.2 (2016): 309-321. <http://eudml.org/doc/277132>.

@article{HortensiaGaleana2016,
abstract = {For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph CC(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and CC(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.},
author = {Hortensia Galeana-Śanchez, Rocío Sánchez-López},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; kernel perfect digraph; kernel by monochromatic paths; color-class digraph; quasi color-perfect digraph; color-perfect digraph},
language = {eng},
number = {2},
pages = {309-321},
title = {Kernels by Monochromatic Paths and Color-Perfect Digraphs},
url = {http://eudml.org/doc/277132},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Hortensia Galeana-Śanchez
AU - Rocío Sánchez-López
TI - Kernels by Monochromatic Paths and Color-Perfect Digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 309
EP - 321
AB - For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph CC(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and CC(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.
LA - eng
KW - kernel; kernel perfect digraph; kernel by monochromatic paths; color-class digraph; quasi color-perfect digraph; color-perfect digraph
UR - http://eudml.org/doc/277132
ER -

References

top
  1. [1] P. Arpin and V. Linek, Reachability problems in edge-colored digraphs, Discrete Math. 307 (2007) 2276-2289. doi:10.1016/j.disc.2006.09.042[Crossref][WoS] Zbl1127.05049
  2. [2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000). Zbl0958.05002
  3. [3] C. Berge, Graphs (North-Holland, Amsterdan, 1989). 
  4. [4] C. Berge and P. Duchet, Perfect graphs and kernels, Bull. Inst. Math. Acad. Sin. 16 (1988) 263-274. 
  5. [5] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31. doi:10.1016/0012-365X(90)90346-J[Crossref] Zbl0721.05027
  6. [6] E. Boros and V. Gurvich, Perfect graphs, kernels and cores of cooperative games, RUTCOR Research Report 12 (Rutgers University, April 2003). Zbl1103.05034
  7. [7] V. Chvátal, On the computational complexity of finding a kernel, Report CRM300, Centre de Recherches Math´ematiques (Universit´e de Montr´eal, 1973). 
  8. [8] P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101. doi:10.1016/S0167-5060(08)70041-4[Crossref] 
  9. [9] A.S. Fraenkel, Planar Kernel and Grundy with d ≤ 3, dout ≤ 2, din ≤ 2, are NP- complete, Discrete Appl. Math. 3 (1981) 257-262. doi:10.1016/0166-218X(81)90003-2[Crossref] 
  10. [10] A.S. Fraenkel, Combinatorial games: Selected bibliography with a succinct gourmet introduction, Electron J. Combin. 14 (2009) DS2. 
  11. [11] 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] Zbl0529.05024
  12. [12] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-112. doi:10.1016/0012-365X(95)00036-V[Crossref] Zbl0857.05054
  13. [13] 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] Zbl0958.05061
  14. [14] H. Galeana-Sánchez, Kernels by monochromatic paths and the color-class digraph, Discuss. Math. Graph Theory 31 (2011) 273-281. doi:10.7151/dmgt.1544[Crossref] Zbl1234.05111
  15. [15] H. Galeana-Sánchez and R. Rojas-Monroy, A counterexample to a conjecture on edge-coloured tornaments, Discrete Math. 282 (2004) 275-276. doi:10.1016/j.disc.2003.11.015[Crossref] Zbl1042.05039
  16. [16] S. Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. The- ory Ser. B 45 (1988) 108-111. doi:10.1016/0095-8956(88)90059-7[Crossref] 
  17. [17] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944). Zbl0063.05930
  18. [18] V. Neumann-Lara, Seminúcleos de una digráfica, An. Inst. Mat. 11 (1971) 55-62. 
  19. [19] M. Richardson, Solutions of irreflexive relations, Ann. of Math. (2) 58 (1953) 573-590. doi:10.2307/1969755[Crossref] Zbl0053.02902
  20. [20] M. Richardson, Extensions theorems for solutions of irreflexive relations, Proc. Natl. Acad. Sci. USA 39 (1953) 649-655. doi:10.1073/pnas.39.7.649[Crossref] 
  21. [21] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge coloured digraphs, J. Combin. Theory Ser. B 33 (1982) 271-275. doi:10.1016/0095-8956(82)90047-8[Crossref] Zbl0488.05036

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.