| Autor: |
Charbit, Pierre, Thomassé, Stéphan |
| Rok vydání: |
2024 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
