Monochromatic absorbency and independence in 3-quasi-transitive digraphs
Por:
Galeana-Sánchez H., O'Reilly-Regueiro E.
Publicada:
1 ene 2013
Categoría:
Discrete Mathematics and Combinatorics
Resumen:
We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. In an m-coloured digraph D we say that a subdigraph H is: monochromatic whenever all of its arcs are coloured alike, and almost monochromatic if with at most 1 exception all of its arcs are coloured with the same colour. If D is an m-coloured digraph a kmp or a kernel by monochromatic paths of D is a set K of vertices of D which is independent by monochromatic paths (for any two different vertices u, v 2 K there are no monochromatic paths between them) such that for every other vertex x 2 V (D) \K there is a vertex v 2 K such that there is an xv monochromatic directed path in D. A digraph D is 3-quasi-transitive if whenever (x, y), (y,w), and (w, z) 2 A(D) with x, y,w and z pairwise different vertices, either (x, z) or (z, x) is in A(D), and it is asymmetric if it has no symmetric arcs. In 1982, Sands, Sauer, and Woodrow proved that every 2-coloured tournament has a kmp. They also posed the following problem: Let T be a 3-coloured tournament which does not contain C3 (the 3-coloured cyclic tournament of order 3). Then, must T contain a kmp? In this paper we consider asymmetric 3-quasi-transitive digraphs, which not only generalise tournaments but also bipartite tournaments, and prove that if D is an m-coloured asymmetric 3-quasi-transitive digraph such that every C4 (the directed cycle of length 4) is monochromatic and every C3 (the directed cycle of length 3) is almost monochromatic, then D has a kernel by monochromatic paths. We also note that the hypotheses on C3 and C4 are tight.
Filiaciones:
Galeana-Sánchez H.:
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la Investigacin Científica Circuito Exterior, Ciudad Universitaria, Coyoacán 04510, México, D.F, Mexico
O'Reilly-Regueiro E.:
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la Investigacin Científica Circuito Exterior, Ciudad Universitaria, Coyoacán 04510, México, D.F, Mexico
|