MISC

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} <= 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
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000240523500022&DestApp=WOS_CPL

エクスポート
BibTeX RIS