# On monochromatic paths and bicolored subdigraphs in arc-colored tournaments

Pietra Delgado-Escalante; Hortensia Galeana-Sánchez

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 4, page 791-820
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPietra Delgado-Escalante, and Hortensia Galeana-Sánchez. "On monochromatic paths and bicolored subdigraphs in arc-colored tournaments." Discussiones Mathematicae Graph Theory 31.4 (2011): 791-820. <http://eudml.org/doc/271022>.

@article{PietraDelgado2011,

abstract = {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.},

author = {Pietra Delgado-Escalante, Hortensia Galeana-Sánchez},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {kernel; kernel by monochromatic paths; tournament; arc-colored tournament; tournament kernel},

language = {eng},

number = {4},

pages = {791-820},

title = {On monochromatic paths and bicolored subdigraphs in arc-colored tournaments},

url = {http://eudml.org/doc/271022},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Pietra Delgado-Escalante

AU - Hortensia Galeana-Sánchez

TI - On monochromatic paths and bicolored subdigraphs in arc-colored tournaments

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 4

SP - 791

EP - 820

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

LA - eng

KW - kernel; kernel by monochromatic paths; tournament; arc-colored tournament; tournament kernel

UR - http://eudml.org/doc/271022

ER -

## References

top- [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. Zbl0721.05027
- [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] 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] 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. Zbl1213.05108
- [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. Zbl0456.05032
- [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] 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. Zbl0770.05050
- [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] 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] 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] 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] 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] 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] 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] 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] 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] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combin. 60 (2001) 137-147. Zbl1068.05504
- [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. Zbl0509.05048
- [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] 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. Zbl0654.05033
- [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. Zbl1241.91002
- [29] M. Richardson, Solutions of irreflexive relations, Annals of Math. 58 (1953) 573-590, doi: 10.2307/1969755. Zbl0053.02902
- [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] 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. Zbl1174.05114
- [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] 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

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.