2023/09/28 by Harutyunyan, Ararat, Surroca, Gil Puig i
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.16565
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 ε>0 and 2≤ k≤ n1/2-ε, the list dichromatic number of KG(n,k) is Θ(nln 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≥ 2 and m≥max\lnρr,2\, the list dichromatic number of the complete r-partite graph with m vertices in each part is Θ(rln m), extending a classical result of Alon. Finally, we give a directed analogue of Sabidussi's theorem on the chromatic number of graph products.