Acyclic and complete coloring of digraphs with the minimum and maximum possible numbers of colors
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |