Nicolas Almeida Martins

dblp:137/5079 · DBLP profile ↗
← Back
11ranked-venue papers
1as first author
8since 2021 · last 2026
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 11 · 1 first-author · 8 since 2021Databases, data management, data science and information retrieval · 1 · 1 since 2021
YearPublicationVenuePosition
2026 The harmonious coloring game
Cláudia Linhares Sales, Thiago Braga Marcilon, Nicolas Almeida Martins, Nicolas Nisse, Rudini Menezes Sampaio
Inf. Process. Lett.3
2026 The Normal Domination Game in graphs
João Marcos Brito, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio
J. Comput. Syst. Sci.3
2025 The Graph Coloring Game on 4 x n-Grids
abstract
The graph coloring game is a famous two-player game (re)introduced by Bodlaender in 1991. Given a graph G and k ϵ N , Alice and Bob alternately (starting with Alice) color an uncolored vertex with some color in {1, • • •, k] such that no two adjacent vertices receive a same color. If eventually all vertices are colored, then Alice wins and Bob wins otherwise. The game chromatic number χ g (G) is the smallest integer k such that Alice has a winning strategy with k colors in G . It has been recently (2020) shown that, given a graph G and k ϵ N, deciding whether χ g (G) ≤ k is PSPACE-complete. Surprisingly, this parameter is not well understood even in “simple” graph classes. Let P n denote the path with n ≥ 1 vertices. For instance, in the case of Cartesian grids, it is easy to show that χ g ( P m □ P n ) ≤ 5 since χ g (G) ≤ ∆ + 1 for any graph G with maximum degree ∆. However, the exact value is only known for small values of m , namely χ g (P 1 □ P n ) = 3, χ g (P 2 □ P n ) = 4 and χ g ( P 3 □ Pn ) = 4 for n ≥ 4 [Raspaud, Wu, 2009]. Here, we prove that, for every n ≥ 18, χ g ( P 4 □ P n ) = 4.
Caroline Brosse, Nicolas Almeida Martins, Nicolas Nisse, Rudini Menezes Sampaio
LAGOS2
2025 The Convex Set Forming Game
Caroline Brosse, Nicolas Almeida Martins, Nicolas Nisse, Rudini Menezes Sampaio
Theor. Comput. Sci.2
2023 The connected greedy coloring game
Carlos V. G. C. Lima, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio
Theor. Comput. Sci.3
2022 Spy game: FPT-algorithm, hardness and graph products
Eurinardo Rodrigues Costa, Nicolas Almeida Martins, Rudini Menezes Sampaio
Theor. Comput. Sci.2
2022 PSPACE-hardness of variants of the graph coloring game
Carlos V. G. C. Lima, Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio
Theor. Comput. Sci.3
2021 Spy Game: FPT-Algorithm and Results on Graph Products
Eurinardo Rodrigues Costa, Nicolas Almeida Martins, Rudini Menezes Sampaio
COCOON2
2020 Hardness of Variants of the Graph Coloring Game
Thiago Braga Marcilon, Nicolas Almeida Martins, Rudini Menezes Sampaio
LATIN2
2018 Spy-game on graphs: Complexity and simple topologies
Nathann Cohen, Nicolas Almeida Martins, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes, Rudini Menezes Sampaio
Theor. Comput. Sci.2
2018 Locally identifying coloring of graphs with few P4s
Nicolas Almeida Martins, Rudini Menezes Sampaio
Theor. Comput. Sci.1