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

On H-Coloring Problems with H Expressed by Complements of Cycles, Bipartite Graphs, and Chordal Graphs On H-Problemas de coloração com H Expressado por complementos de ciclos, gráficos bipartidos e gráficos de cordas

Akihiro UEJIMA, Hiro ITO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

O problema de coloração é um conhecido problema de otimização combinatória de grafos. Este artigo considera Problemas de coloração H, que são problemas de coloração com restrições tais que alguns pares de cores não podem ser usados ​​para vértices adjacentes. A restrição de cores adjacentes pode ser representada por um gráfico H, ou seja, cada vértice representa uma cor e cada aresta significa que as duas cores correspondentes aos dois vértices finais podem ser usadas para vértices adjacentes. Especialmente, H-problema de colorir com um gráfico completo H de ordem k é equivalente ao tradicional k-problema de coloração. Este artigo apresenta condições suficientes para que H-o problema de coloração pode ser reduzido a um H-problema de coloração, onde H é um subgrafo de H. E mostra uma hierarquia sobre classes de H-gráficos coloridos para qualquer gráfico de complemento H de um ciclo de ordem ímpar n 5.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1026-1030
Data de publicação
2002/05/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria

autores

Palavra-chave