Cycle reversions and dichromatic number in tournaments. (March 2019)

• Record Type: Journal Article
• Authors: Ellis, Paul; Soukup, Dániel T.
• Is Part Of: European journal of combinatorics. Volume 77(2019)
• Page Start: 31
• Page End: 48
• Publication Date: 2019-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.10.008
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We show that if D is a tournament of arbitrary size then D can be made to have only finite strong components after reversing a locally finite sequence of cycles. In turn, we prove that the vertex set of any tournament can be covered by two acyclic induced subgraphs after reversing a locally finite sequence of cycles. This provides a partial solution to a conjecture of S. Thomassé.