1. Dichromatic Number and Cycle Inversions
- Author
-
Charbit, Pierre and Thomassé, Stéphan
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics ,05C15, 05C20 ,G.2.2 - Abstract
The results of this note were stated in the first author PhD manuscript in 2006 but never published. The writing of a proof given there was slightly careless and the proof itself scattered across the document, the goal of this note is to give a short and clear proof using Farkas Lemma. The first result is a characterization of the acyclic chromatic number of a digraph in terms of cyclic ordering. Using this theorem we prove that for any digraph, one can sequentially reverse the orientations of the arcs of a family of directed cycles so that the resulting digraph has acyclic chromatic number at most 2.
- Published
- 2024