Cycle Reversions and Dichromatic Number in (Infinite) Tournaments

16.11.2017 15:00 - 16:30

P. Ellis (Manhattanville College, New York, US)

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 \(\\\) 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.

Organiser:

KGRC

Location:
SR 101, 2. St., Währinger Str. 25