On monochromatic paths and bicolored subdigraphs in arc-colored tournaments

Pietra Delgado-Escalante ; Hortensia Galeana-Sánchez

Discussiones Mathematicae Graph Theory, Tome 31 (2011), p. 791-820 / Harvested from The Polish Digital Mathematics Library

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

Publié le : 2011-01-01

Zbl 1259.05068

EUDML-ID : urn:eudml:doc:271022

Bibliographie

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

[001] [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. | Zbl 0721.05027

[002] [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. | Zbl 0886.05089

[003] [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. | Zbl 1103.05034

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

[005] [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. | Zbl 1213.05108

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

[007] [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. | Zbl 0456.05032

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

[009] [10] A.S. Fraenkel, Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction, The Electronic Journal of Combinatorics, 14 (Dynamic Survey DS2), 2007.

[010] [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. | Zbl 0770.05050

[011] [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. | Zbl 0857.05054

[012] [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. | Zbl 0529.05024

[013] [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. | Zbl 0593.05034

[014] [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. | Zbl 0928.05032

[015] [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. | Zbl 1049.05042

[016] [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. | Zbl 1042.05039

[017] [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. | Zbl 1075.05033

[018] [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. | Zbl 1152.05028

[019] [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. | Zbl 1042.05049

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

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

[022] [23] M. Kwaśnik, The generalization of Richardson theorem, Discuss. Math. IV (1981) 11-14. | Zbl 0509.05048

[023] [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. | Zbl 0508.05038

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

[025] [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. | Zbl 0654.05033

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

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

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

[029] [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. | Zbl 0488.05036

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

[031] [32] I. Włoch, On imp-sets and kernels by monochromatic paths of the duplication, Ars Combin. 83 (2007) 93-100. | Zbl 1174.05114

[032] [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. | Zbl 1152.05033

[033] [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. | Zbl 1213.05118