Geodesic
Kernels by Monochromatic Paths and Color-Perfect Digraphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 309-321.

Voir la notice de l'article provenant de la source Library of Science

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 C(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 C(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.
Keywords: kernel, kernel perfect digraph, kernel by monochromatic paths, color-class digraph, quasi color-perfect digraph, color-perfect digraph 
@article{DMGT_2016_36_2_a4,
     author = {Galeana-\'Sanchez, Hortensia and S\'anchez-L\'opez, Roc{\'\i}o},
     title = {Kernels by {Monochromatic} {Paths} and {Color-Perfect} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {309--321},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a4/}
}
TY  - JOUR
AU  - Galeana-Śanchez, Hortensia
AU  - Sánchez-López, Rocío
TI  - Kernels by Monochromatic Paths and Color-Perfect Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 309
EP  - 321
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a4/
LA  - en
ID  - DMGT_2016_36_2_a4
ER  - 
%0 Journal Article
%A Galeana-Śanchez, Hortensia
%A Sánchez-López, Rocío
%T Kernels by Monochromatic Paths and Color-Perfect Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 309-321
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a4/
%G en
%F DMGT_2016_36_2_a4
Galeana-Śanchez, Hortensia; Sánchez-López, Rocío. Kernels by Monochromatic Paths and Color-Perfect Digraphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 309-321. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a4/

[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

[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000).

[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

[6] E. Boros and V. Gurvich, Perfect graphs, kernels and cores of cooperative games, RUTCOR Research Report 12 (Rutgers University, April 2003).

[7] V. Chvátal, On the computational complexity of finding a kernel, Report CRM300, Centre de Recherches Mathématiques (Université de Montréal, 1973).

[8] P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101. doi:10.1016/S0167-5060(08)70041-4

[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

[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

[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

[13] H. Galeana-Sánchez, Kernels in edge coloured digraphs, Discrete Math. 184 (1998) 87-99. doi:10.1016/S0012-365X(97)00162-3

[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

[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

[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

[17] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944).

[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

[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

[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