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
Existem vários tipos de coloração de dígrafos, como coloração de vértices e coloração de arcos. Chamamos uma coloração de arco de um dígrafo G o primeiro tipo se for uma atribuição de cores ao conjunto de arcos de G em que não há dois arcos consecutivos da mesma cor. Em algumas pesquisas, a coloração do arco do primeiro tipo tem sido associada ao número mínimo da coloração de vértices denominado número cromático. Considerando a classe dos dígrafos lineares, uma coloração de arco de um dígrafo G do primeiro tipo é equivalente à coloração de vértices de seu dígrafo de linha L(G). Neste artigo, estudamos a coloração de arcos do primeiro tipo e a coloração de vértices de dígrafos lineares. Damos o limite superior do número cromático de L(G) pelo número cromático de um dígrafo G que admite loops. Também é mostrado que existe um número inteiro bastante pequeno k de modo que o dígrafo de linha iterado Lk(G) pode ser colorido com 3 vértices. Como consequência, derivamos o número cromático dos dígrafos de de Bruijn e Kautz.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -