Let $G=(V, E)$ be an acyclic digraph (DAG) with all in- and out-degrees at most $k$. Is it true that the edges of $G$ may be always colored properly in $2k$ colors?


In the discussion of [this](https://mathoverflow.net/a/442170/4312) question it is proved (for $k=2$, but the proofs work verbatim for other values of $k$) that $G$ has $|E|/(2k)$ disjoint edges.



Chromatic index of an acyclic digraph
Here is a solution (obtained while discussing the question with my colleague András Sebő).


Consider the undirected graph $H$ obtained from $G$ as follows: the partite sets of $H$ are two copies $V\_1$ and $V\_2$ of $V(G)$, and for each arc $(u,v)$ in $G$ we add an edge in $H$ between the copy of $u$ in $V\_1$ and the copy of $v$ in $V\_2$.


The graph $H$ is bipartite and has maximum degree $k$. By [Kőnig's theorem](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)) $H$ has a proper $k$-edge-coloring, that is a partition of its edges into $k$ matchings $M\_1,\ldots,M\_k$. The edges of $H$ are in bijection with the arcs of $G$, and if we consider the image of each matching $M\_i$ in $G$ we obtain a subgraph of $G$ with in-degree and out-degree at most 1 (that is, a disjoint union of directed cycles and directed paths). As $G$ is acyclic, the image of each matching $M\_i$ in $G$ is a union of paths, so the edges of $G$ can be partitioned into $k$ subgraphs, each being a union of paths. As a union of paths is 2-edge-colorable, $G$ has a partition of its edges into $k$ 2-edge-colorable subgraphs, and is therefore $2k$-edge-colorable, as desired.


