On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees

• The maximum arc-chromatic number of k-digraphs is determined for infinite many k.
• We give a better upper bound of the arc-chromatic number of (k,kk,k)-digraphs.
• A conjecture about the arc-chromatic number of k-digraphs holds for almost all k.
• Another conjecture about (k,kk,k)-digraphs holds for infinite many k.
• The known upper bounds are close to the exact values.

A k-digraph is a digraph in which every vertex has outdegree at most k  , and a (k∨l)(k∨l)-digraph is a digraph in which every vertex has either outdegree at most k or indegree at most l. The maximum arc-chromatic number of digraphs over the k  -digraphs and the (k∨l)(k∨l)-digraphs are denoted by Φ(k)Φ(k) and Φ∨(k,l)Φ∨(k,l), respectively. In this paper we first show that Φ(k)=θ(2k)=2tΦ(k)=θ(2k)=2t when k=(2t−1t−1) for t≥2t≥2, where θ   is the function defined by θ(n)=min⁡{t:(t⌊t/2⌋)≥n}. Then we prove that Φ∨(k,k)≤θ(2k)+1Φ∨(k,k)≤θ(2k)+1 for k≥1k≥1. The corollary of these results proves weaker versions of two conjectures of Bessy et al., i.e., Φ(k+1)≤Φ(k)+1Φ(k+1)≤Φ(k)+1 holds for almost all k  , and Φ∨(k,k)≤Φ(k)+1Φ∨(k,k)≤Φ(k)+1 holds when k=(2t−1t−1) for t≥2t≥2.