Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors

2025/08/22 by Olsen, Mika, Rubio-Montiel, Christian, Ramirez, Alejandra Silva
#05C15 #05C20 #05C76 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.16043

Abstract

The dichromatic and diachromatic numbers of a digraph are the minimum and maximum numbers of colors, respectively, in acyclic and complete colorings of the digraph. In this paper, we construct, for all r ≤ t, non-symmetric digraphs with dichromatic number r and diachromatic number t. Moreover, we discuss the existence of asymmetric digraphs with dichromatic number r and diachromatic number t ≥ r , establishing a quadratic upper bound b(r) ≤ t .

Citations

• The smallest 5-chromatic tournament

Related

• On the dib-chromatic number of a digraph
• Acyclic Coloring of Products of Digraphs and of Digraphs with Bounded Treewidth
• The dib-chromatic number of digraphs
• Coloring of a Digraph
• Acyclic coloring of special digraphs