Partitions, Functions and the Arc-Coloring of Digraphs
H. KAWAI · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2006
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) = o 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.