2006年9月

# Partitions, functions and the arc-coloring of digraphs

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
• Hiroyuki Kawai
• ,
• Yukio Shibata

E89A
9

2381

2385

DOI
10.1093/ietfec/e89-a.9.2381

IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

Let f and g be two maps from a set E into a set F such that f(v) not equal g(x) for every x in E. Sahili [8] has shown that, if mini{vertical bar f(-1)(z)vertical bar, vertical bar g(-1)(z)vertical bar} &lt;= n for each z epsilon F, then E can be partitioned into at most 2n + 1 sets E-1..., E2+1 such that f(E-i) boolean AND g(E-i) = 0 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.

リンク情報
DOI
https://doi.org/10.1093/ietfec/e89-a.9.2381
Web of Science