27 citations · 38 across the 13 of their papers we have counts for
6 papers · 1 filter
Hull Games of Induced Path Convexities in Graphs
Eurinardo Costa, Leon Almeida, Rudini Sampaio
In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths. In 2024,…
Characterizations of graph classes via convex geometries: a survey
Mitre C. Dourado, Marisa Gutierrez, Fábio Protti +2
Graph convexity has been used as an important tool to better understand the structure of classes of graphs. Many studies are devoted to determine if a graph equipped with a convexi…
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…
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…
Complexity aspects of the triangle path convexity
Mitre C. Dourado, Rudini M. Sampaio
A path is a {\em triangle path} (respectively, {\em monophonic path}) of if no edges exist joining vertices and of such that ;…
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…