Voltar
Artigo Acesso aberto Produção Nacional
BIBTEX RIS

A complexidade do número cromático orientado para subgrafos de grades

2022; Linguagem: Português

10.5540/03.2022.009.01.0229

ISSN

2359-0793

Autores

E. M. M. Coelho, H. Coelho, M. P. Ferreira, Laiz de Oliveira Machado Leiva de Faria, S. Klein,

Tópico(s)

graph theory and CDMA systems

Resumo

Seja G = (V, A) um grafo orientado e G o grafo subjacente de G . Uma k-coloração- → orientada de G é uma partição de V em k partes de maneira que não existem dois vértices adjacentes pertencendo a mesma parte e todos os arcos entre um par de partes tem a mesma orientação. O número cromático orientado χo ( G ) de G é o menor k, tal que G admite uma k-coloração orientada. O número cromático orientado de G, denotado por χo (G), é o maior χo ( G ) para todas orientações − → − → G de G. Neste trabalho mostramos que decidir se χo ( G ) ≤ k é um problema N P -completo mesmo −→quando G é um subgrafo de uma grade.

Referência(s)