Reducing the dichromatic number via cycle reversions in infinite digraphs

We prove the following conjecture of S. Thomassé: for every (potentially infinite) digraph $D$ it is possible to iteratively reverse directed cycles in such a way that the dichromatic number of the final reorientation $D^{*}$ of $D$ is at most two and each edge is flipped only finitely many times. In addition, we guarantee that in every strong component of $D^{*}$ all the local edge-connectivities are finite and any edge is reversed at most twice.

No reviews yet.

No comments yet.