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

Autores

  • E. M. M. Coelho
  • H. Coelho
  • M. P. Ferreira
  • L. Faria
  • S. Klein

DOI:

https://doi.org/10.5540/03.2022.009.01.0229

Palavras-chave:

Grafo Orientado, Número Cromático Orientado, Grafos Grade.

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.

Downloads

Não há dados estatísticos.

Biografia do Autor

E. M. M. Coelho

UFG, Goiânia, GO

H. Coelho

UFG, Goiânia, GO

M. P. Ferreira

UFG, Goiânia, GO

L. Faria

UERJ, UFRJ - Rio de Janeiro, RJ

S. Klein

UERJ, UFRJ - Rio de Janeiro, RJ

Referências

S. N. Bhatt e S. S. Cosmadakis. “The complexity of minimizing wire lengths in VLSI layouts”.

Em: Information Processing Letters 25.4 (1987), pp. 263–267. doi: https://doi.org/

1016/0020-0190(87)90173-6.

S. A. Cook. “The complexity of theorem-proving procedures”. Em: Proceedings of the

third annual ACM symposium on Theory of computing. 1971, pp. 151–158. doi:

1145/800157.805047.

G. Fertin, A. Raspaud e A. Roychowdhury. “On the oriented chromatic number of grids”. Em:

Information Processing Letters 85.5 (2003), pp. 261–266. doi: https://doi.org/10.

/S0020-0190(02)00405-2.

M. R. Garey e D. S. Johnson. “The rectilinear Steiner tree problem is NP-complete”. Em:

SIAM Journal on Applied Mathematics 32.4 (1977), pp. 826–834. doi: https://doi.

org/10.1137/0132071.

W. Klostermeyer e G. MacGillivray. “Homomorphisms and oriented colorings of equivalence

classes of oriented graphs”. Em: Discret. Math. 274.1-3 (2004), pp. 161–172. doi: https:

//doi.org/10.1016/S0012-365X(03)00086-4.

Downloads

Publicado

2022-12-08

Edição

Seção

Trabalhos Completos