On the dib-chromatic number of a digraph
Juan José Montellano-Ballesteros, Christian Rubio-Montiel · 2025
Read On the dib-chromatic number of a digraph by Juan José Montellano-Ballesteros, Christian Rubio-Montiel (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-2511-08807.txt.
Introduction
Juan José Montellano-Ballesteros and Christian Rubio-Montiel study a coloring number for directed graphs built around mutual reachability between color classes. In a dib-coloring, each color class must contain a vertex that points toward every other class and a vertex that all other classes point toward, while the coloring stays acyclic.
The dib-chromatic number is the largest number of colors such a coloring can use. The authors first answer a basic question that the definition leaves open: whether this number always exists. They then work out the dib-chromatic number for bipartite digraphs, the two-sided directed graphs that model many matching and ordering problems. The paper is a contribution to structural graph theory, where new coloring invariants are tested on the graph families that reveal their behavior.
Catalog record
| CREATOR | Juan José Montellano-Ballesteros, Christian Rubio-Montiel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-08807
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the dib-chromatic number of a digraph Juan José Montellano-Ballesteros, Christian Rubio-Montiel Abstract An acyclic coloring of a digraph that maximizes the number of colors such that each color class has a vertex pointing to all other classes and a vertex pointing to it from all other classes is known as the dib-chromatic number of a digraph. In this paper, we answer the question about the existence of the dib-chromatic number and study the dib-chromatic number of bipartite digraphs. Keywords. Complete coloring, acyclic coloring, b -chromatic number, irreducible coloring. Mathematics Subject Classification. 05C15, 05C20. 1 Introduction Chromatic graph theory requires ways to optimize the search for its parameters; one way is through algorithms. For instance, we would like to perform an operation to reduce the number of colors in a graph with a given proper coloring. One way to achieve this is by recoloring its vertices, not necessarily in a greedy way, but by distributing the vertices of a single color to the rest of the color classes. Of course, such recoloring is not feasible if such a color class contains a vertex with neighbors to all other color classes; such a vertex is called a b -vertex . A b -coloring of a given graph is a coloring of the vertices such that in each color class there exists a b -vertex. The b -chromatic number of the graph G is defined as the worst case for the number of colors used by this coloring heuristic method, equivalently defined as the maximum k such that a proper b -coloring using k colors is accepted, and denoted by b(G) . Note that, if G is a graph with a proper coloring using \chi(G) colors, such a coloring is a b -coloring. The study of the b -chromatic number emerged in the late 1990s [ 7 ] where its complexity was determined. Since then, several papers have expanded its study, for example [ 9 , 12 , 13 ] . It has been of interest to extend the chromatic number to the theory of digraphs [ 10 , 11 ] , as it has been for other coloring parameters [ 1 , 2 , 3 , 16 , 17 ] . For instance, the dichromatic number dc is a generalization of the chromatic number for a graph, where a proper coloring in graphs corresponds to an acyclic coloring in a digraph D and the goal is to find the minimum number of colors \text{dc}(D) used in this type of coloring introduced by Neumann-Lara [ 16 ] and by Erdős [ 4 ] when they showed that in a tournament T_{n} then \text{dc}(T_{n})=O(\frac{n}{\lg n}) , also see [ 8 ] . In an acyclic coloring of D with \text{dc}(D) colors, there are arcs in both directions between each pair of color classes, giving rise to the extension of complete coloring of graphs to digraphs [ 5 , 6 ] . In [ 1 ] , the achromatic number \text{dac}(D) of a digraph D is defined as the maximum over the acyclic and complete colorings in D , showing results such as in a tournament T_{n} then \text{dac}(T_{n})=\Omega(\frac{n}{\lg n}) . To generalize the b -chromatic number from an algorithmic point of view, one could define a “ b -vertex” with respect to an acyclic coloring of a digraph D as a u vertex colored i such that u\cup C_{j} contains a directed cycle for each color class C_{j} , i\not=j . However, if we consider a directed cycle \overrightarrow{C}_{3} , with an acyclic coloring using two colors, the singular color class is a “ b -vertex” but the other color class has no “ b -vertices”. In [ 10 ] , a vertex u is called a b^{+} -vertex with respect to a coloring \Gamma of a digraph D if u is incident to a vertex colored with each color different from the color of u . Analogously, a vertex v is a b^{-} -vertex with respect to \Gamma if v is incident from a vertex colored with each color different from the color of v . A b -coloring of D is a coloring such that each color class contains a b^{+} -vertex and a b^{-} -vertex. The dib -chromatic number of D , denoted by \text{dib}(D) , is the maximum k such that D admits an acyclic b -coloring with k colors. The question then arises as to the existence of the \text{dib}(D) for a given digraph D . This paper is divided as follows. Section 2 presents the existence of the dib-chromatic number. Section 3 addresses the study of the dib-chromatic number in bipartite digraphs, including simple bipartite digraphs. 2 Existence In this section, we will show that for any given digraph D , the dib-chromatic number \text{dib}(D) of D exists, by showing that \text{dc}(D)\leq\text{dib}(D) , where \text{dc}(D) is the dichromatic number of D . We consider finite, and loopless digraphs, i.e., digraphs where digons are permitted. Let D=(V(D),E(D)) be a digraph and r\geq 2 be an integer. An acyclic coloring \Gamma of V(D) using r colors will be called b -irreducible if there is no other acyclic coloring \Gamma^{\prime} of V(D) using r-1 colors such that, for each i\in[r-1]:=\{1,\dots,r-1\} , \Gamma^{-1}(i)\subseteq\Gamma^{\prime-1}(i) . Given an acyclic coloring of V(D) using r colors and i\in[r] , we will say that a vertex x\in\Gamma^{-1}(i) is a b -vertex if it is a b^{+} -vertex and a b^{-} -vertex, and a pair of vertices \{x,y\}\subseteq\Gamma^{-1}(i) will be called a b -pair if x is a b^{+} -vertex and y is a b^{-} -vertex. Recall that the out-neighborhood of a vertex x of D is N^{+}_{D}(x)=\{y\in V(D)\colon xy\in E(D)\} , and its in-neighborhood is N^{-}_{D}(x)=\{y\in V(D)\colon yx\in E(D)\} . Lemma 1 . Let D be a digraph and \Gamma:V(D)\rightarrow[r] be an acyclic coloring of D using r colors. If \Gamma is b -irreducible, then \Gamma is a b -coloring of D . Proof. Let D be a digraph, \Gamma:V(D)\rightarrow[r] be an acyclic b -irreducible coloring of D using r colors and let us suppose there is no b -vertex nor b -pair in \Gamma^{-1}(r) . For each x\in\Gamma^{-1}(r) let V^{-}_{b}(x)=\{j\in[r-1]:N_{D}^{-}(x)\cap\Gamma^{-1}(j)=\emptyset\} and V^{+}_{b}(x)=\{j\in[r-1]:N_{D}^{+}(x)\cap\Gamma^{-1}(j)=\emptyset\} . Observe that since there is no b -vertices in \Gamma^{-1}(r) , it follows that for every x\in\Gamma^{-1}(r) we have that V^{+}_{b}(x)\not=\emptyset or V^{-}_{b}(x)\not=\emptyset . Claim 2 . Either for every x\in\Gamma^{-1}(r) we have V^{+}_{b}(x)\not=\emptyset , or for every x\in\Gamma^{-1}(r) we have V^{-}_{b}(x)\not=\emptyset . Suppose there is x\in\Gamma^{-1}(r) where V^{+}_{b}(x)=\emptyset . Hence, for every j\in[r-1] it follows that N_{D}^{+}(x)\cap\Gamma^{-1}(j)\not=\emptyset . That is, x is a b^{+} -vertex. Since there is no b -pairs in \Gamma^{-1}(r) it follows that for each y\in\Gamma^{-1}(r)\setminus\{x\} there is i_{y}\in[r-1] such that N_{D}^{-}(y)\cap\Gamma^{-1}(i_{y})=\emptyset . That is, for every y\in\Gamma^{-1}(r)\setminus\{x\} we have V^{-}_{b}(y)\not=\emptyset . Finally, since x is not a b -vertex, there is i\in[r-1] such that N_{D}^{-}(x)\cap\Gamma^{-1}(i)=\emptyset . Thus V^{-}_{b}(x)\not=\emptyset and the claim follows. By the previous claim, without loss of generality, we suppose that for every x\in\Gamma^{-1}(r) we have V^{+}_{b}(x)\not=\emptyset . Let B_{1}=\{x\in\Gamma^{-1}(r):1\in V^{+}_{b}(x)\} and, for 1<j\leq r-1 , let B_{j}=\{x\in\Gamma^{-1}(r):j\in V^{+}_{b}(x)\}\setminus\bigcup\limits_{1\leq i<j}B_{i} . Observe that since for every x\in\Gamma^{-1}(r) we have V^{+}_{b}(x)\not=\emptyset , it follows that \{B_{1},\dots,B_{r-1}\} is a set of pairwise disjoint sets whose union