Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments |
| |
Authors: | Hortensia Galeana-Sánchez Rocío Rojas-Monroy |
| |
Affiliation: | (1) Instituto de Matemáticas, UNAM, Ciudad Universitaria, Circuito Exterior, 04510, México, D.F., México;(2) Facultad de Ciencias, Universidad Autónoma del Estado de México, Instituto Literario No. 100, Centro, 50000 Toluca, Edo. de México, México |
| |
Abstract: | We call the tournament T an m-coloured tournament if the arcs of T are coloured with m-colours. If v is a vertex of an m-coloured tournament T, we denote by ξ(v) the set of colours assigned to the arcs with v as an endpoint. In this paper is proved that if T is an m-coloured tournament with |ξ(v)|≤2 for each vertex v of T, and T satisfies at least one of the two following properties (1) m≠3 or (2) m=3 and T contains no C3 (the directed cycle of length 3 whose arcs are coloured with three distinct colours). Then there is a vertex v of T such that for every other vertex x of T, there is a monochromatic directed path from x to v. Received: April, 2003 |
| |
Keywords: | Kernel Kernel-perfect digraph Kernel by monochromatic paths Tournament m-Coloured tournament |
本文献已被 SpringerLink 等数据库收录! |
|