Número de Grundy impróprio de subclasses de cografos

  • Efraim Rodrigues UFC
  • Cláudia Linhares Sales UFC

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á
Publicado
30/06/2020
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.