Reducing the dichromatic number via cycle reversions in infinite digraphs

DOI10.1016/J.EJC.2020.103196MaRDI QIDQ2225401zbMATH OpenOpenAlexFDO

Authors Paul Ellis, Attila Joó, Dániel T. Soukup

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1909.00873

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Infinite graphs (05C63)

Abstract: We prove the following conjecture of S. Thomass'e: 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^{\ast }$ 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^{\ast }$ all the local edge-connectivities are finite and any edge is reversed at most twice.

Recommendations

• Cycle reversions and dichromatic number in tournaments
• Dichromatic number and fractional chromatic number
• On some unsolved and solved problems in the theory of directed graphs. I
• On partitioning the edges of an infinite digraph into directed cycles
• A note on coloring digraphs of large girth

Cites work

• 2-partition-transitive tournaments
• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• Cycle reversions and dichromatic number in tournaments
• Elementary submodels in infinite combinatorics
• Infinite combinatorics plain and simple
• Menger's theorem for infinite graphs
• On Better-Quasi-Ordering Countable Series-Parallel Orders
• Orientations of graphs with uncountable chromatic number
• Planar digraphs of digirth four are 2-colorable
• The dichromatic number of a digraph

Cited in

(2)

• Cycle reversions and dichromatic number in tournaments
• scientific article; zbMATH DE number 22956 (Why is no real title available?)

This page was built for publication: Reducing the dichromatic number via cycle reversions in infinite digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225401)