Kernels by Monochromatic Directed Paths in 3-Colored Tournaments and Quasi-Tournaments
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 endpoint, ζ − (v) the set of colours assigned to the arcs with v as final vertex, and ζ + (v) the set of colours assigned to the arcs with v as an initial vertex. In this paper, we prove that if T is a 3-coloured tournament which does not contain C3 such that: 1. for each v ∈ V(T) |ζ − (v) |≤ 2,
A proof of the Erdős-Sands-Sauer-Woodrow conjecture
Abstract A very nice result of Barany and Lehel asserts that every finite subset X or R d can be covered by h ( d ) X-boxes (i.e. each box has two antipodal points in X). As shown by Gyarfas and Palvőlgyi this result would follow from the following conjecture: If a tournament admits a partition of its arc set into k quasi-orders, then its domination number is bounded in terms of k. This question is in turn implied by the Erdős–Sands–Sauer–Woodrow conjecture: If the arcs of a tournament T are coloured with k colour's, there is a set X of at most g ( k ) vertices such that for every vertex v of T, there is a monochromatic path from X to v. We give a short proof of this statement. We moreover show that the general Sands–Sauer–Woodrow conjecture (which as a special case implies the stable marriage theorem) is valid for directed graphs with bounded stability number. This conjecture remains however open.
Une generalisation du theoreme de Richardson sur l'existence de noyaux dans les graphes orientes
Richardson's theorem [4] asserts that if a digraph has no odd circuit, it possesses a kernel. We improve this theorem in the following manner: if each odd circuit has two short crossing chords, i.e. two chords of the type (X"i,X"i"+"2), (X"i"+"1,X"i"+"3), it possesses a kernel.