Let f and g be two maps from a set E into a set F such that f(x) g(x) for every x in E. Sahili [8] has shown that, if min {|f-1(z)|,|g-1(z)|}≤ n for each z∈ F, then E can be partitioned into at most 2n+1 sets E1,..., E2n+1 such that f(Ei)∩ g(Ei)= for each i=1,..., 2n+1. He also asked if 2n+1 is the best possible bound. By using Sahili's formulation of the problem in terms of the chromatic number of line digraphs, we improve the upper bound from 2n+1 to O(log n). We also investigate extended version for more than two maps.

There are several kinds of coloring of digraphs, such as vertex-coloring and arc-coloring. We call an arc-coloring of a digraph G the first type if it is an assignment of colors to the arc set of G in which no two consecutive arcs have the same color. In some researches, the arc-coloring of first type has been associated with the minimum number of the vertex-coloring called chromatic number. Considering the class of line digraphs, an arc-coloring of a digraph G of the first type is equivalent to the vertex-coloring of its line digraph L(G). In this paper, we study the arc-coloring of the first type and the vertex-coloring of line digraphs. We give the upper bound of the chromatic number of L(G) by the chromatic number of a digraph G which admits loops. It is also shown that there exists quite a small integer k so that the iterated line digraph Lk(G) is 3-vertex-colorable. As a consequence, we derive the chromatic number of de Bruijn and Kautz digraphs.