On monochromatic paths and bicolored subdigraphs in arc-colored tournaments

Delgado-Escalante, Pietra ; Galeana-Sánchez, Hortensia

Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 4, pp. 791-820.

Résumé

Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic and bicolor coloration. We also prove that our conditions are not mutually implied and that they are not implied by those known previously. Besides some open problems are proposed.

Détail

Mots-clés : kernel, kernel by monochromatic paths, tournament

Bibliographie

[1] C. Berge, Graphs (Nort-Holland, Amsterdam, third edition, 1991).

[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.

[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.

[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.

[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] 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.

[7] P. Duchet, Représentations, Noyaux en Théorie des Graphes et Hypergraphes, PhD thesis, Univ. Paris 6 (Paris, 1979).

[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.

[9] A.S. Fraenkel, Planar kernel and Grundy with d ≤ 3, $d_{out} ≤ 2$, $d_{in} ≤ 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, The Electronic Journal of Combinatorics, 14 (Dynamic Survey DS2), 2007.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[21] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147.

[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] M. Kwaśnik, The generalization of Richardson theorem, Discuss. Math. IV (1981) 11-14.

[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.

[25] J. van Leeuwen, Having a Grundy-numbering is NP-complete, Report, 207, Computer Science Dept., Pennsylvania State University, (University Park, PA, 1976).

[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.

[27] V. Neumann-Lara, Semin'ucleos y n'ucleos, Anales del Instituto de Matemáticas UNAM 11 (1971) 55-62.

[28] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behaviour, Princeton University Press (Princeton, 1947) 2nd edition.

[29] M. Richardson, Solutions of irreflexive relations, Annals of Math. 58 (1953) 573-590, doi: 10.2307/1969755.

[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.

[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] I. Włoch, On imp-sets and kernels by monochromatic paths of the duplication, Ars Combin. 83 (2007) 93-100.

[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.

[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.