2 papers
cs.CC2024
The complexity of convexity number and percolation time in the cycle convexity
Carlos V. G. C. Lima, Thiago Marcilon, Pedro Paulo de Medeiros
The subject of graph convexity is well explored in the literature, the so-called interval convexities above all. In this work, we explore the cycle convexity, an interval convexity…
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…