Clique number of tournaments
Clique number of tournaments
The dichromatic number of a directed graph D is the minimum integer k such that the
vertex set of D can be partitioned into k acyclic subdigraphs. It is easy to see
that the chromatic number of a graph G is the dichromatic number of the digraph
obtained from G by replacing each edge with a digon (two anti-parallel arcs). Based
on this simple observation, many theorems concerning the chromatic number of undirected
graphs have been generalized to digraphs via dichromatic number. However, no concept
analogous to clique number for digraphs has been available. The purpose of this
presentation is to explore such a concept and its relationship with the dichromatic
number, mirroring the relationship between the clique number and the chromatic number in
undirected graphs. We will focus, in particular, on studying the notion of χ-boundedness.