Monochromatic Paths and Monochromatic Cycles in Edge-Coloured \(k\)-Partite Tournaments

Hortensia Galeana-Sanchez1, Rocio Rojas-Monroy1,2
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 de] Estado de México Instituto Literario No. 100, 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 subdigraph \(H\) of \(D\) is called monochromatic if all of its arcs are coloured alike.

A set \(N \subseteq V(D)\) is said to be a kernel by monochromatic paths if it satisfies the following two conditions:

(i) For every pair of different vertices \(u,v \in N\) there is no monochromatic directed path between them.

(ii) For every vertex \(x \in V(D) – N\), there is a vertex \(y \in N\) such that there is an \(xy\)-monochromatic directed path.

In this paper, it is proved that if \(D\) is an \(m\)-coloured \(k\)-partite tournament such that every directed cycle of length \(3\) and every directed cycle of length \(4\) is monochromatic, then \(D\) has a kernel by monochromatic paths.

Some previous results are generalized.