Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909748690944000 |
|---|---|
| author | Olsen, Mika Rubio-Montiel, Christian Ramirez, Alejandra Silva |
| author_facet | Olsen, Mika Rubio-Montiel, Christian Ramirez, Alejandra Silva |
| contents | 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 \leq 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 \geq r $, establishing a quadratic upper bound $ b(r) \leq t $. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16043 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors Olsen, Mika Rubio-Montiel, Christian Ramirez, Alejandra Silva Combinatorics 05C15, 05C20, 05C76 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 \leq 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 \geq r $, establishing a quadratic upper bound $ b(r) \leq t $. |
| title | Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors |
| topic | Combinatorics 05C15, 05C20, 05C76 |
| url | https://arxiv.org/abs/2508.16043 |