A complexidade do número cromático orientado para subgrafos de grades
DOI:
https://doi.org/10.5540/03.2022.009.01.0229Keywords:
Grafo Orientado, Número Cromático Orientado, Grafos Grade.Abstract
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
References
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.
