A Simple Construction of Tournaments with Finite and Uncountable Dichromatic Number

Abstract

The dichromatic number $\chi (\vec{G})$ of a digraph $\vec{G}$ is the minimum number of colors needed to color the vertices $V(\vec{G})$ in such a way that no monochromatic directed cycle is obtained. In this note, for any $k\in \mathbb{N}$, we give a simple construction of tournaments with dichromatic number exactly equal to $k$. The proofs are based on a combinatorial lemma on partitioning a checkerboard which may be of independent interest. We also generalize our finite construction to give an elementary construction of a complete digraph of cardinality equal to the cardinality of $\mathbb{R}$ and having an uncountable dichromatic number. Furthermore, we also construct an oriented balanced complete $n$-partite graph ${\vec{K}}_n^{(m)}$, such that the minimum number of colors needed to color its vertices such that there is no monochromatic directed triangle is greater than or equal to $nm/(n+2m-2)$.

8 pages, 1 figure