Discussiones Mathematicae Graph Theory 31(2) (2011)
273281
doi: 10.7151/dmgt.1544
Hortensia GaleanaSánchez
Instituto de Matemáticas 
A set S ⊆ V(D) is a kernel by monochromatic paths whenever the two following conditions hold:
1.

2.

In this paper it is introduced the concept of colorclass digraph to prove that if D is an mcolored strongly connected finite digraph such that:
(i)

(ii)

This result generalizes a classical result by Sands, Sauer and Woodrow which asserts that any 2colored digraph has a kernel by monochromatic paths, in case that the digraph D be a strongly connected digraph.
Keywords: kernel, kernel by monochromatic paths, the colorclass digraph
2010 Mathematics Subject Classification: 05C20.
[1]  J.M. Le Bars, Counterexample of the 01 law for fragments of existential secondorder logic; an overview, Bull. Symbolic Logic 9 (2000) 6782, doi: 10.2307/421076. 
[2]  J.M. Le Bars, The 01 law fails for frame satisfiability of propositional model logic, Proceedings of the 17th Symposium on Logic in Computer Science (2002) 225234, doi: 10.1109/LICS.2002.1029831. 
[3]  C. Berge, Graphs (NorthHolland, Amsterdam, 1985). 
[4]  E. Boros and V. Gurvich, Perfect graphs, kernels and cores of cooperative games, Discrete Math. 306 (2006) 23362354, doi: 10.1016/j.disc.2005.12.031. 
[5]  A.S. Fraenkel, Combinatorial game theory foundations applied to digraph kernels, Electronic J. Combin. 4 (2) (1997) #R10. 
[6]  A.S. Fraenkel, Combinatorial games: selected bibliography with a succint gourmet introduction, Electronic J. Combin. 14 (2007) #DS2. 
[7]  G. Hahn, P. Ille and R. Woodrow, Absorbing sets in arccoloured tournaments, Discrete Math. 283 (2004) 9399, doi: 10.1016/j.disc.2003.10.024. 
[8]  H. GaleanaSánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103112, doi: 10.1016/0012365X(95)00036V. 
[9]  H. GaleanaSánchez, Kernels in edgecoloured digraphs, Discrete Math. 184 (1998) 8799, doi: 10.1016/S0012365X(97)001623. 
[10]  H. GaleanaSánchez and R. RojasMonroy, A counterexample to a conjecture on edgecoloured tournaments, Discrete Math. 282 (2004) 275276, doi: 10.1016/j.disc.2003.11.015. 
[11]  H. GaleanaSánchez and R. RojasMonroy, On monochromatic paths and monochromatic 4cycles in edge coloured bipartite tournaments, Discrete Math. 285 (2004) 313318, doi: 10.1016/j.disc.2004.03.005. 
[12]  G. Gutin and J. BangJensen, Digraphs: Theory, Algorithms and Applications (SpringerVerlag, London, 2001). 
[13]  T.W. Haynes, T. Hedetniemi and P.J. Slater, Domination in Graphs (Advanced Topics, Marcel Dekker Inc., 1998). 
[14]  T.W. Haynes, T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., 1998). 
[15]  J. von Leeuwen, Having a Grundy Numbering is NPcomplete, Report 207 Computer Science Department, University Park, PA, 1976, Pennsylvania State University. 
[16]  B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edgecoloured digraphs, J. Combin. Theory (B) 33 (1982) 271275, doi: 10.1016/00958956(82)900478. 
[17]  I. Włoch, On impsets and kernels by monochromatic paths in duplication, Ars Combin. 83 (2007) 9399. 
Received 24 November 2009
Revised 2 December 2010
Accepted 27 January 2011