Counterexample to a conjecture on edge-coloured tournaments

Abstract

We call the tournament T an m-coloured tournament if the arcs of T are coloured with m colours. In this paper we prove that for each n greater than or equal to 6, there exists a 4-coloured tournament T-n of order n satisfying the two following conditions: (1) T-n does not contain C-3 (the directed cycle of length 3, whose arcs are coloured with three distinct colours), and (2) T-n does not contain any vertex v such that for every other vertex x of T-n there is a monochromatic directed path from x to v. This answers a question proposed by Shen Minggang in 1988. (C) 2004 Elsevier B.V. All rights reserved.