The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] arc-coloring(1hit)

1-1hit
  • Partitions, Functions and the Arc-Coloring of Digraphs

    Hiroyuki KAWAI  Yukio SHIBATA  

     
    PAPER-Graphs and Networks

      Vol:
    E89-A No:9
      Page(s):
    2381-2385

    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.