The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
정점 색칠, 호 색칠 등 이중문자의 색칠에는 여러 종류가 있습니다. 우리는 이중그래프의 원호 색칠이라고 부릅니다. G 호 세트에 색상을 할당하는 경우 첫 번째 유형 G 두 개의 연속된 호는 같은 색을 갖지 않습니다. 일부 연구에서는 첫 번째 유형의 원호 색칠이 유채색수라고 불리는 정점 색칠의 최소 개수와 연관되어 있습니다. 선수음자의 종류를 고려하여 수음자의 원호채색 G 첫 번째 유형은 선 digraph의 정점 색상과 동일합니다. L(G). 본 논문에서는 첫 번째 유형의 원호 색칠과 선 이중 그래프의 꼭지점 색칠에 대해 연구한다. 우리는 색수(chromatic number)의 상한을 제공합니다. L(G) 이중 그래프의 색채 수로 G 루프를 허용합니다. 또한 아주 작은 정수가 존재하는 것으로 나타났습니다. k 그래서 반복된 선 이중 그래프는 Lk(G)은 3개의 꼭짓점 색상을 지정할 수 있습니다. 결과적으로 우리는 de Bruijn과 Kautz digraph의 색수를 유도합니다.
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.
부
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 Lk(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
부
@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 Lk(G) is 3-vertex-colorable. As a consequence, we derive the chromatic number of de Bruijn and Kautz digraphs.},
keywords={},
doi={},
ISSN={},
month={June},}
부
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 Lk(G) is 3-vertex-colorable. As a consequence, we derive the chromatic number of de Bruijn and Kautz digraphs.
ER -