A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

The Chromatic Number and the Chromatic Index of de Bruijn and Kautz Digraphs O Número Cromático e o Índice Cromático dos Dígrafos de De Bruijn e Kautz

Hiroyuki KAWAI, Yukio SHIBATA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.6 pp.1352-1358
Data de publicação
2002/06/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Gráficos e Redes

autores

Palavra-chave