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

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

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.


Palavras-chave


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

Texto completo:

PDF

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.




DOI: https://doi.org/10.5540/03.2022.009.01.0229

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato