Partitions, Functions and the Arc-Coloring of Digraphs

Hiroyuki KAWAI, Yukio SHIBATA

Summary :

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 E₁,..., E_2n+1 such that f(E_i)∩ g(E_i)= 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.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.9 pp.2381-2385
• Publication Date: 2006/09/01
• Online ISSN: 1745-1337
• DOI: 10.1093/ietfec/e89-a.9.2381
• Type of Manuscript: PAPER
• Category: Graphs and Networks

Authors

Hiroyuki KAWAI
Yukio SHIBATA

Keyword

arc-coloring,  set partition,  line digraph