Discussiones Mathematicae Graph Theory 29(2) (2009) 337-347

MONOCHROMATIC PATHS AND MONOCHROMATIC SETS OF ARCS IN 3-QUASITRANSITIVE DIGRAPHS

Hortensia Galeana-Sánchez1,R. Rojas-Monroy2 and B. Zavala1

1Instituto de Matemáticas
Universidad Nacional Autónoma de México
Ciudad Universitaria, México, D.F. 04510, México

2Facultad de Ciencias
Universidad Autónoma del Estado de México
Instituto Literario, Centro 50000, Toluca, Edo. de México, México

Abstract

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A+(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured 3-quasitransitive digraph such that for every vertex u of D, A+(u) is monochromatic and D satisfies some colouring conditions over one subdigraph of D of order 3 and two subdigraphs of D of order 4, then D has a kernel by monochromatic paths.

Keywords: m-coloured digraph, 3-quasitransitive digraph, kernel by monochromatic paths, γ-cycle, quasi-monochromatic digraph.

2000 Mathematics Subject Classification: 05C15, 05C20.

References

[1] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141-161, doi: 10.1002/jgt.3190200205.
[2] J. Bang-Jensen and J. Huang, Kings in quasi-transitive digraphs, Discrete Math. 185 (1998) 19-27, doi: 10.1016/S0012-365X(97)00179-9.
[3] C. Berge, Graphs (North Holland, Amsterdam, New York, 1985).
[4] P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4.
[5] P. Duchet, Classical Perfect Graphs, An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67-96.
[6] 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.
[7] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V.
[8] H. Galeana-Sánchez, Kernels in edge coloured digraphs, Discrete Math. 184 (1998) 87-99, doi: 10.1016/S0012-365X(97)00162-3.
[9] H. Galena-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.
[10] 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.
[11] H. Galeana-Sánchez, R. Rojas-Monroy and B. Zavala, Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs, submitted.
[12] Ghouilá-Houri, Caractérisation des graphes non orientés dont on peut orienter les aretes de maniére à obtenir le graphe d'une relation d'ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371.
[13] S. Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7.
[14]M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953) 573, doi: 10.2307/1969755.
[15]M. Richardson, Extensions theorems for solutions of irreflexive relations, Proc. Nat. Acad. Sci. USA 39 (1953) 649, doi: 10.1073/pnas.39.7.649.
[16] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8.

Received 6 November 2007
Revised 26 February 2009
Accepted 27 February 2009