Dichromatic Number and Cycle Inversions
CoRR(2024)
摘要
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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要