Número de Grundy impróprio de subclasses de cografos
Resumo
O problema de coloração d-imprópria de vértices, que permite que uma cor atribuída a um vértice possa ser compartilhada com até d, d≥0, de seus vizinhos, é uma generalização do problema clássico de coloração de vértices (onde d=0). Sendo igualmente intratável, a heurística de coloração gulosa d-imprópria foi introduzida em [Rodrigues 2020]. Neste trabalho, determinamos o seu pior desempenho em algumas subclasses de cografos.
Palavras-chave:
coloração gulosa, coloração defectiva, coloração imprópria, cografos
Referências
Christen, C. A. and Selkow, S. M. (1979). Some perfect coloring properties of graphs.Journal of Combinatorial Theory, Series B, 27(1):49 – 59.
Corneil, D., Lerchs, H., and Burlingham, L. (1981). Complement reducible graphs.Dis-crete Applied Mathematics, 3(3):163 – 174.
Cowen, L., Goddard, W., and Jesurum, C. E. (1997). Defective coloring revisited.Journalof Graph Theory, 24(3):205–219.
Cowen, L. J., Cowen, R. H., and Woodall, D. R. (1986). Defective colorings of graphsin surfaces: Partitions into subgraphs of bounded valency.Journal of Graph Theory,10(2):187–195.
Goyal, N. and Vishwanathan, S. (1997). NP-completeness of undirected grundy numbe-ring and related problems.Unpublished manuscript.
Grundy, P. M. (1939). Mathematics and games.Eureka, 2:6–9.
Karp, R. M. (1972).Reducibility among Combinatorial Problems, pages 85–103. Sprin-ger US, Boston, MA.
Rodrigues, E. (2020). Coloração k-imprópria gulosa. Dissertação de Mestrado, MDCC - Universidade Federal do Ceará
Corneil, D., Lerchs, H., and Burlingham, L. (1981). Complement reducible graphs.Dis-crete Applied Mathematics, 3(3):163 – 174.
Cowen, L., Goddard, W., and Jesurum, C. E. (1997). Defective coloring revisited.Journalof Graph Theory, 24(3):205–219.
Cowen, L. J., Cowen, R. H., and Woodall, D. R. (1986). Defective colorings of graphsin surfaces: Partitions into subgraphs of bounded valency.Journal of Graph Theory,10(2):187–195.
Goyal, N. and Vishwanathan, S. (1997). NP-completeness of undirected grundy numbe-ring and related problems.Unpublished manuscript.
Grundy, P. M. (1939). Mathematics and games.Eureka, 2:6–9.
Karp, R. M. (1972).Reducibility among Combinatorial Problems, pages 85–103. Sprin-ger US, Boston, MA.
Rodrigues, E. (2020). Coloração k-imprópria gulosa. Dissertação de Mestrado, MDCC - Universidade Federal do Ceará
Publicado
30/06/2020
Como Citar
RODRIGUES, Efraim; SALES, Cláudia Linhares.
Número de Grundy impróprio de subclasses de cografos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 17-20.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11079.
