# 2017 seminar talk: Cycle Reversions and Dichromatic Number in (Infinite) Tournaments

Talk held by Paul Ellis (Manhattanville College, New York, USA) at the KGRC seminar on 2017-11-16.

### Abstract

The dichomatic number for a digraph is the least number of acyclic subgraphs needed
to cover the graph. In 2005, Pierre Charbit showed that by iterating the operation $\{\{$select a
directed cycle, and reverse the direction of each arc in it$\}\}$ that the dichromatic number in
any finite digraph can be lowered to 2. This is optimal, as a single directed cycle will
always have dichromatic number 2. Recently, Daniel Soukup and I showed that the same is true
for infinite *tournaments* of any cardinality, and in fact, we proved this by induction. Along
the way to proving this, we uncovered some nice structural facts about infinite digraphs that
we think are of more general interest. While this talk will be mostly graph theoretic in
flavor, we did need to put on our set theory glasses to distinguish between the singular and
regular cases in the induction. I should note that the question remains open for arbitrary
inifinite digraphs, even those of countable cardinality.