Reducing the dichromatic number via cycle reversions in infinite digraphs. (December 2020)

• Record Type: Journal Article
• Authors: Ellis, Paul; Joó, Attila; Soukup, Dániel T.
• Is Part Of: European journal of combinatorics. Volume 90(2020)
• Publication Date: 2020-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103196
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 reversed 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.