Reducing the dichromatic number via cycle reversions in infinite digraphs

Link:
Autor/in:
Erscheinungsjahr:
2020
Medientyp:
Text
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/openAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/e29cf5b0-5e7b-4a39-8325-756af6ba2b28