# 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

## Access Full Article

top## Abstract

top## How to cite

topHortensia 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] 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] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000). Zbl0958.05002
- [3] C. Berge, Graphs (North-Holland, Amsterdan, 1989).
- [4] C. Berge and P. Duchet, Perfect graphs and kernels, Bull. Inst. Math. Acad. Sin. 16 (1988) 263-274.
- [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] E. Boros and V. Gurvich, Perfect graphs, kernels and cores of cooperative games, RUTCOR Research Report 12 (Rutgers University, April 2003). Zbl1103.05034
- [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] P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101. doi:10.1016/S0167-5060(08)70041-4[Crossref]
- [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] A.S. Fraenkel, Combinatorial games: Selected bibliography with a succinct gourmet introduction, Electron J. Combin. 14 (2009) DS2.
- [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] 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] 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] 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] 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] 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] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944). Zbl0063.05930
- [18] V. Neumann-Lara, Seminúcleos de una digráfica, An. Inst. Mat. 11 (1971) 55-62.
- [19] M. Richardson, Solutions of irreflexive relations, Ann. of Math. (2) 58 (1953) 573-590. doi:10.2307/1969755[Crossref] Zbl0053.02902
- [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] 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 ?

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