The improper Grundy number of subclasses of cographs

• Efraim Rodrigues UFC
• Cláudia Linhares Sales UFC

DOI: https://doi.org/10.5753/etc.2020.11079

Abstract

The d-improper vertex coloring problem, where a color assigned to a vertex can be shared with at most d, d≥ 0, of its neighbors, is a generalization of the classic vertex coloring problem (set d=0). Being equally intractable, the greedy d-improprer coloring heuristic was introduced in [Rodrigues 2020]. In this work, we study the worst performance of this heuristic on some subclasses of cographs.

Keywords: greedy coloring, defective coloring, improper coloring, cographs

References

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á