3 papers
cs.DM2021
Algorithms, hardness and graph products on a pursuit-evasion game
Eurinardo Costa, Nicolas Martins, Rudini Sampaio
In the -spy game over a graph, introduced by Cohen et al. in 2016, one spy and guards occupy vertices of a graph and, at each turn, each guard may move along one edge an…
cs.DM2019
Hardness of some variants of the graph coloring game
Thiago Marcilon, Nicolas Martins, Rudini Sampaio
Very recently, a long-standing open question proposed by Bodlaender in 1991 was answered: the graph coloring game is PSPACE-complete. In 2019, Andres and Lock proposed five variant…
cs.DM2011
Fixed parameter algorithms for restricted coloring problems
Victor Campos, Cláudia Linhares-Sales, Ana Karolinna Maia +2
In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number, the Thue chromatic number, the harmonious chromatic number…