On monochromatic paths in edge-coloured digraphs |
| |
Authors: | B Sands N Sauer R Woodrow |
| |
Institution: | Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta T2N 1N4, Canada |
| |
Abstract: | Let G be a directed graph whose edges are coloured with two colours. Call a set S of vertices of Gindependent if no two vertices of S are connected by a monochromatic directed path. We prove that if G contains no monochromatic infinite outward path, then there is an independent set S of vertices of G such that, for every vertex x not in S, there is a monochromatic directed path from x to a vertex of S. In the event that G is infinite, the proof uses Zorn's lemma. The last part of the paper is concerned with the case when G is a tournament. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|