On unavoidable graphs and tournaments

Abstract

Ramsey's theorem asserts that every sufficiently large graph contains either a large complete graph or its complement as an induced subgraph. There are many variants of Ramsey's theorem. If we consider connected graphs, one knows that every large connected graph contains either a large complete graph, a large star or a long path as an induced subgraph. We call a theorem of this type a Ramsey-type theorem. In the first part of this thesis, we present new results on Ramsey-type theorems.

In the second part of this thesis, we study tournaments with large chromatic number. The chromatic number of a tournament T is the minimum number of transitive subsets of V(T) covering all vertices of T. A class H of tournaments is heroic if every tournament containing none of the members of H has bounded chromatic number. In [3], Every heroic set with one tournament is explicitly characterized. In this thesis, we investigate heroic sets containing two tournaments.

The third result is on tournaments with large domination number. The domination number of a tournament T is the minimum size of S⊆V(T) such that every vertex outside of S has an in-neighbor in S. A tournament T is a rebel if every tournament not containing T has bounded domination number. We investigate the following conjecture of Hehui Wu: every tournament is a rebel. We prove that the conjecture is false in general but every 2-colorable tournament is a rebel. Moreover we show that there is a rebel which is not 2-colorable.