The search functionality is under construction.

The search functionality is under construction.

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 Bruijn and Kautz digraphs.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.6 pp.1352-1358

- Publication Date
- 2002/06/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Graphs and Networks

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hiroyuki KAWAI, Yukio SHIBATA, "The Chromatic Number and the Chromatic Index of de Bruijn and Kautz Digraphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 6, pp. 1352-1358, June 2002, doi: .

Abstract: 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 Bruijn and Kautz digraphs.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_6_1352/_p

Copy

@ARTICLE{e85-a_6_1352,

author={Hiroyuki KAWAI, Yukio SHIBATA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={The Chromatic Number and the Chromatic Index of de Bruijn and Kautz Digraphs},

year={2002},

volume={E85-A},

number={6},

pages={1352-1358},

abstract={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 Bruijn and Kautz digraphs.},

keywords={},

doi={},

ISSN={},

month={June},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1352

EP - 1358

AU - Hiroyuki KAWAI

AU - Yukio SHIBATA

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E85-A

IS - 6

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - June 2002

AB - 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 Bruijn and Kautz digraphs.

ER -