Cycle reversions and dichromatic number in tournaments
| Autor: | Dániel T. Soukup, Paul Ellis |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Vertex (graph theory)
Mathematics::Combinatorics Conjecture 010102 general mathematics Mathematics - Logic 0102 computer and information sciences 05C20 05C63 05C15 05C38 03E05 01 natural sciences Finite sequence Combinatorics Computer Science::Discrete Mathematics 010201 computation theory & mathematics Partial solution FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Tournament Reversing Combinatorics (math.CO) 0101 mathematics Logic (math.LO) Computer Science::Databases Mathematics |
| Zdroj: | European Journal of Combinatorics. 77:31-48 |
| ISSN: | 0195-6698 |
| Popis: | We show that if $D$ is a tournament of arbitrary size then $D$ has finite strong components after reversing a locally finite sequence of cycles. In turn, we prove that any tournament can be covered by two acyclic sets after reversing a locally finite sequence of cycles. This provides a partial solution to a conjecture of S. Thomass\'e. Comment: 23 pages, first public version. Comments are very welcome |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect