The Chromatic Number and the Chromatic Index of de Bruijn and Kautz Digraphs

概要

論文の詳細を見る
There are several kinds of coloring of digraphs, such as vertex-coloring and arc-coloring. We call an arc-coloring of a digraph G the first type if it is an assignment of colors to the arc set of G in which no two consecutive arcs have the same color. In some researches, the arc-coloring of first type has been associated with the minimum number of the vertex-coloring called chromatic number. Considering the class of line digraphs, an arc-coloring of a digraph G of the first type is equivalent to the vertex-coloring of its line digraph L(G). In this paper we study the arc-coloring of the first type and the vertex-coloring of line digraphs. We give the upper bound of the chromatic number of L(G) by the chromatic number of a digraph G which admits loops. It is also shown that there exists quite a small integer k so that the iterated line digraph L^k(G) is 3-vertex-colorable. As a consequence, we derive the chromatic number of de Bruijo and Kautz digraphs.
社団法人電子情報通信学会の論文
2002-06-01