Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2309.16565 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913799787773952 |
|---|---|
| author | Harutyunyan, Ararat Surroca, Gil Puig i |
| author_facet | Harutyunyan, Ararat Surroca, Gil Puig i |
| contents | The dichromatic number of a digraph $D$ is the smallest $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs, and the dichromatic number of an undirected graph is the maximum dichromatic number over all its orientations. Extending a well-known result of Lovász, we show that the dichromatic number of the Kneser graph $KG(n,k)$ is $Θ(n-2k+2)$ and that the dichromatic number of the Borsuk graph $BG(n+1,a)$ is $n+2$ if $a$ is large enough. We then study the list version of the dichromatic number. We show that, for any $\varepsilon>0$ and $2\leq k\leq n^{1/2-\varepsilon}$, the list dichromatic number of $KG(n,k)$ is $Θ(n\ln n)$. This extends a recent result of Bulankina and Kupavskii on the list chromatic number of $KG(n,k)$, where the same behaviour was observed. We also show that for any $ρ>3$, $r\geq 2$ and $m\geq\max\{\ln^ρr,2\}$, the list dichromatic number of the complete $r$-partite graph with $m$ vertices in each part is $Θ(r\ln m)$, extending a classical result of Alon. Finally, we give a directed analogue of Sabidussi's theorem on the chromatic number of graph products. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_16565 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Colouring Complete Multipartite and Kneser-type Digraphs Harutyunyan, Ararat Surroca, Gil Puig i Combinatorics The dichromatic number of a digraph $D$ is the smallest $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs, and the dichromatic number of an undirected graph is the maximum dichromatic number over all its orientations. Extending a well-known result of Lovász, we show that the dichromatic number of the Kneser graph $KG(n,k)$ is $Θ(n-2k+2)$ and that the dichromatic number of the Borsuk graph $BG(n+1,a)$ is $n+2$ if $a$ is large enough. We then study the list version of the dichromatic number. We show that, for any $\varepsilon>0$ and $2\leq k\leq n^{1/2-\varepsilon}$, the list dichromatic number of $KG(n,k)$ is $Θ(n\ln n)$. This extends a recent result of Bulankina and Kupavskii on the list chromatic number of $KG(n,k)$, where the same behaviour was observed. We also show that for any $ρ>3$, $r\geq 2$ and $m\geq\max\{\ln^ρr,2\}$, the list dichromatic number of the complete $r$-partite graph with $m$ vertices in each part is $Θ(r\ln m)$, extending a classical result of Alon. Finally, we give a directed analogue of Sabidussi's theorem on the chromatic number of graph products. |
| title | Colouring Complete Multipartite and Kneser-type Digraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2309.16565 |