Dichromatic Number and Cycle Inversions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910309821710336 |
|---|---|
| author | Charbit, Pierre Thomassé, Stéphan |
| author_facet | Charbit, Pierre Thomassé, Stéphan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15130 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dichromatic Number and Cycle Inversions Charbit, Pierre Thomassé, Stéphan Combinatorics Discrete Mathematics 05C15, 05C20 G.2.2 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. |
| title | Dichromatic Number and Cycle Inversions |
| topic | Combinatorics Discrete Mathematics 05C15, 05C20 G.2.2 |
| url | https://arxiv.org/abs/2401.15130 |