On monochromatic paths and bicolored subdigraphs in arc-colored tournaments

 Access to full text

 Full (PDF)

1. [1] C. Berge, Graphs (Nort-Holland, Amsterdam, third edition, 1991). 
2. [2] 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. Zbl0721.05027
3. [3] E. Boros and V. Gurvich, A corrected version of the Duchet kernel conjecture, Discrete Math. 179 (1998) 231-233, doi: 10.1016/S0012-365X(97)00094-0. Zbl0886.05089
4. [4] E. Boros and V. Gurvich, Perfect graphs, kernels and cores of cooperative games, RUTCOR Research Report, 12, Rutgers University, New Jersey, april 2003. Dedicated to the memory of Claude Berge. Zbl1103.05034
5. [5] V. Chvátal, On the computational complexity of finding a kernel, Report, CRM-300, Centre de Recherches Mathématiques Université de Montréal (Montréal, 1973). 
6. [6] P. Delgado-Escalante and H. Galeana-Sánchez, Kernels and cycles' subdivisions in arc-colored tournaments, Discuss. Math. Graph Theory 29 (2009) 101-117, doi: 10.7151/dmgt.1435. Zbl1213.05108
7. [7] P. Duchet, Représentations, Noyaux en Théorie des Graphes et Hypergraphes, PhD thesis, Univ. Paris 6 (Paris, 1979). 
8. [8] 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
9. [9] A.S. Fraenkel, Planar kernel and Grundy with d ≤ 3, $d_{out}\le 2$, $d_{in}\le 2$ are NP-complete, Discrete Appl. Math. 3 (1981) 257-262, doi: 10.1016/0166-218X(81)90003-2. 
10. [10] A.S. Fraenkel, Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction, The Electronic Journal of Combinatorics, 14 (Dynamic Survey DS2), 2007. 
11. [11] H. Galeana-Sánchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110 (1992) 251-255, doi: 10.1016/0012-365X(92)90713-P. Zbl0770.05050
12. [12] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge colored tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V. Zbl0857.05054
13. [13] 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
14. [14] 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
15. [15] H. Galeana Sánchez and H. Rincón-Mejía, A sufficient condition for the existence of k-kernels in digraphs, Discuss. Math. Graph Theory 18 (1998) 197-204, doi: 10.7151/dmgt.1075. Zbl0928.05032
16. [16] H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and monochromatic 4-cycles in edge-colored bipartite tournaments, Discrete Math. 285 (2004) 313-318, doi: 10.1016/j.disc.2004.03.005. Zbl1049.05042
17. [17] 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
18. [18] H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and at most 2-colored arc sets in edge colored tournaments, Graphs and Combin. 21 (2005) 307-317, doi: 10.1007/s00373-005-0618-z. Zbl1075.05033
19. [19] H. Galeana-Sánchez and R. Rojas-Monroy, Kernels in edge-coloured orientations of nearly complete graphs, Discrete Math. 308 (2008) 4599-4607, doi: 10.1016/j.disc.2007.08.079. Zbl1152.05028
20. [20] G. Hahn and P. Ille and R.E. Woodrow, Absorbing sets in arc-coloured tournaments, Discrete Math. 283 (2004) 93-99, doi: 10.1016/j.disc.2003.10.024. Zbl1042.05049
21. [21] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147. Zbl1068.05504
22. [22] M. Kucharska and M. Kwaśnik, On (k,l)-kernels of special superdigraphs of Pₘ and Cₘ, Discuss. Math. Graph Theory 21 (2001) 95-109, doi: 10.7151/dmgt.1135. 
23. [23] M. Kwaśnik, The generalization of Richardson theorem, Discuss. Math. IV (1981) 11-14. Zbl0509.05048
24. [24] M. Kwaśnik, On (k,l)-kernels of exclusive disjunction, cartesian sum and normal product of two directed graphs, Discuss. Math. V (1982) 29-34. Zbl0508.05038
25. [25] J. van Leeuwen, Having a Grundy-numbering is NP-complete, Report, 207, Computer Science Dept., Pennsylvania State University, (University Park, PA, 1976). 
26. [26] S. Minggang, On monochromatic paths in m-colored tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7. Zbl0654.05033
27. [27] V. Neumann-Lara, Semin'ucleos y n'ucleos, Anales del Instituto de Matemáticas UNAM 11 (1971) 55-62. 
28. [28] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behaviour, Princeton University Press (Princeton, 1947) 2nd edition. Zbl1241.91002
29. [29] M. Richardson, Solutions of irreflexive relations, Annals of Math. 58 (1953) 573-590, doi: 10.2307/1969755. Zbl0053.02902
30. [30] B. Sands, N. Sauer and R.E. Woodrow, On monochromatic paths in edge-colored digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8. Zbl0488.05036
31. [31] A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301, doi: 10.1016/S0012-365X(96)00064-7. 
32. [32] I. Włoch, On imp-sets and kernels by monochromatic paths of the duplication, Ars Combin. 83 (2007) 93-100. Zbl1174.05114
33. [33] I. Włoch, On kernels by monochromatic paths in the corona of digraphs, Central European J. Math. 6 (2008) 537-542, doi: 10.2478/s11533-008-0044-6. Zbl1152.05033
34. [34] I. Włoch and A. Włoch, On (k,l)-kernels in the corona of digraphs, International J. Pure and Appl. Math. 53 (2009) 571-582. Zbl1213.05118

1. Enrique Casas-Bautista, Hortensia Galeana-Sánchez, Rocío Rojas-Monroy, γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs