Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors
Mika Olsen, Christian Rubio-Montiel, Alejandra Silva-Ramírez · 2025
Read Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors by Mika Olsen, Christian Rubio-Montiel, Alejandra Silva-Ramírez (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-16043.txt.
Introduction
Mika Olsen and co-authors present a 2025 math paper on coloring directed graphs. A directed graph has edges with a set direction, like one-way streets. Two coloring goals are studied. One asks for the fewest colors such that each color class has no directed cycles. The other asks for the most colors under a stricter shared rule.
The team builds graphs that are not symmetric and hit any chosen pair of values. The low count can be any value up to the high count. They also ask when lopsided graphs of this kind exist at all. For those, they set a square-based upper bound that ties the two counts. The work settles the range of pairs that can occur.
Catalog record
| CREATOR | Mika Olsen, Christian Rubio-Montiel, Alejandra Silva-Ramírez |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-16043
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors Mika Olsen, Christian Rubio-Montiel, Alejandra Silva-Ramírez 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 r\leq t , non-symmetric digraphs with dichromatic number r r and diachromatic number t t . Moreover, we discuss the existence of asymmetric digraphs with dichromatic number r r and diachromatic number t ≥ r t\geq r , establishing a quadratic upper bound b ( r ) ≤ t b(r)\leq t . Keywords. Acyclic coloring, diachromatic number, non-symmetric digraphs, oriented graphs. 1 Introduction In graph theory, a classical problem is to determine, for two given parameters, whether there exists a (di)graph realizing every valid combination of these parameters. That is, given two graph invariants \varphi and \psi , the goal is to characterize the pairs (\alpha,\beta) for which there exists a (di)graph G such that \varphi(G)=\alpha and \psi(G)=\beta ; see, for example, [ 1 , 11 , 10 , 14 , 20 , 21 ] . A well-known instance of this type of problem considers the minimum and maximum number of colors in a proper and complete vertex coloring: the chromatic number \chi(G) of a graph G is the minimum number of colors in such a coloring, while the achromatic number \psi(G) , introduced by Harary et al. in 1967 [ 12 ] , is the maximum number of colors for such a coloring. In 1979, Bhave [ 6 ] proved that for every pair of integers r\leq t , there exists a graph G such that \chi(G)=r and \psi(G)=t . For further information, we refer the reader to the surveys [ 8 , 13 ] . A natural question is whether this property can be extended to digraphs. We use the notion of acyclic colorings introduced by Neumann-Lara [ 2 ] in 1982 as a natural generalization of proper colorings to digraphs, together with the extension of complete colorings proposed by Edwards [ 9 ] , where a coloring is called complete if, for every ordered pair of distinct colors (i,j) , there exists at least one arc directed from a vertex of color i to a vertex of color j . Recently, in 2019, Araujo-Pardo et al. [ 2 ] formalized the achromatic number for digraphs using acyclic colorings; this generalization applies to all digraphs and preserves the interpolation property known from the undirected case. Following the terminology in [ 2 , 15 ] , the dichromatic number \operatorname{dc}(D) of a digraph D is the minimum number of colors in an acyclic coloring, whereas the diachromatic number \operatorname{dac}(D) is the maximum number of colors in a complete acyclic coloring. In [ 19 ] , Zykov sums were used to construct digraphs realizing specific parameter pairs (r,t) with r\leq t , such that \operatorname{dc}(D)=r and \operatorname{dac}(D)=t . This paper extends to the directed case the classical result asserting that for every pair of integers a\leq b , there exists a graph with chromatic number a and achromatic number b . Since symmetric digraphs coincide with graphs in this context, their dichromatic and diachromatic numbers reduce to the corresponding undirected parameters. We focus our attention on non-symmetric digraphs. First, we prove that for every pair of integers r\leq t , there exists a non-symmetric digraph D such that \operatorname{dc}(D)=r and \operatorname{dac}(D)=t . Second, we provide a quadratic upper bound b(r) such that for every integer t\geq b(r) , there exists an asymmetric digraph D with \operatorname{dc}(D)=r and \operatorname{dac}(D)=t . It is important to observe that these pairs improve the existing known pairs established in [ 19 ] . 2 Definitions and preliminary results In this paper, we consider finite digraphs. Let k be a non-negative integer. An acyclic coloring of a digraph D is a function \varphi:V(D)\to[k] with [k]:=\{1,2,\ldots,k\} . A chromatic class of color i is denoted by C_{i}=\{v\in V(D)\mid\varphi(v)=i\} , for i\in[k] . A sink (resp. source ), in a digraph is a vertex with no outgoing arcs (resp. no incoming arcs). The coloring \varphi is acyclic if no chromatic class induces a subdigraph with a directed cycle. The dichromatic number dc(D) and the diachromatic number dac(D) are the smallest and the largest k such that D admits an acyclic coloring, respectively. An acyclic and complete coloring that uses dc(D) (resp. dac=t ) colors, is an optimal coloring for the dichromatic number (resp. diachromatic number). For general concepts we refer the reader to [ 4 ] and Chapter 12 in [ 7 ] . For two nonempty of vertex sets X,Y of a digraph D , we define [X,Y]=\{(x,y)\in A(D)\mid x\in X,y\in Y\}. Let \mathds{Z}_{m} be the cyclic group of integers modulo m , where m\in\mathds{N} and J is a nonempty subset of \mathds{Z}_{m}\setminus\{0\} such that w\in J if and only if -w\notin J for every w\in\mathds{Z}_{m}\setminus\{0\} . The circulant digraph \overrightarrow{C}_{m}(J) is defined by V(\overrightarrow{C}_{m}(J))=\mathds{Z}_{m}\mbox{ and }A(\overrightarrow{C}_{m}(J))=\{(i,j):i,j\in\mathds{Z}_{m}\mbox{ and }j-i\in J\}. The following results are already known, and we will use them throughout this paper. Theorem 1 . [ 18 ] If T is a regular tournament with 2n+1 vertices, then dc(T)=2 if and only if T\cong\overrightarrow{C}_{2n+1}(1,\ldots,n) . Theorem 2 . [ 2 ] Let T be a circulant tournament or a transitive tournament of order n. Then dac(T)=\left\lceil\frac{n}{2}\right\rceil. The next corollary is a consequence of Theorems 1 and 2 . Corollary 3 . For every t\geq 2 , there exists a 2 -dichromatic tournament with dac(T)=t . Definition 4 . [ 3 ] For every pair of integers r,s with r\geq 3,s\geq 0 ; let H_{p,s}=\overrightarrow{C}_{(r-1)(p+1)+1}(J) for p=(r-2)(s+1)+1 and J=\{1,2,\ldots,p\}\cup\{p+2,p+3,\ldots,2p-s\}\cup\ldots\cup\{(r-2)p+r-1\}. When s=0 , we denote H_{p,s} by H_{r} . Theorem 5 . [ 3 ] For r\geq 3,s\geq 0 , H_{p,s} is a vertex critical r -dichromatic circulant tournament. The next corollary is a consequence of Theorems 2 and 5 . Corollary 6 . For every r\geq 3 and s\geq 0 , there exists a circulant tournament T such that dc(T)=r and dac(T)=\frac{(r^{2}-3r+2)s}{2}+\frac{r^{2}-r+2}{2}. When s=0 , there exists a circulant tournament T with dc(T)=r and dac(T)=(r^{2}-r+2)/2. Table 1 shows the values for the diachromatic number in terms of the dichromatic number, obtained in the Corollary 6 . Note the gaps between the values of the diachromatic number depend on the dichromatic number. dc(T) dac(T) 3 4,5,6,7,8,9… 4 7,10,13,16,19,22… 5 11,17,23,29,35,41… ⋮ 9 37,65,93,121,149,177… ⋮ Table 1: The dc(T) and the dac(T) of the family in Corollary 6 . The next result is a reformulation of the Interpolation Theorem in terms of complete coloring. Theorem 7 . [ 2 ] Let D be a digraph. For every integer l with dc(D)\leq l\leq dac(D) there exists a complete and acyclic coloring with l colors. 3 Construction In this section, we define a construction that allows us to fill the gaps observed in Table 1 . Construction 1 . Let D be a digraph and let P=\{v_{1},v_{2},\ldots,v_{s}\} be a path such that V(D)\cap V(P)=\emptyset . For a non-negative integer n and v_{0}\in V(D) , we define the digraph D_{n}(v_{0}) as follows: \begin{array}[]{ccl}V(D_{n}(v_{0}))&=&V(D)\cup V(P),\\ \\ A(D_{n}(v_{0}))&=&A(D)\cup A(P^{\prime})\cup M,\end{array} where V(P^{{}^{\prime}})=\{v_{0},v_{1},v_{2},\ldots,v_{s}\} and the set