7 papers
On the damage number of graphs
Valentin Gledel, William B. Kinnersley, Balázs Patkós +1
We study a variant of Cops and Robbers in which the robber attempts to visit as many vertices of the graph as possible without being captured, while the cop aims to keep the robber…
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
Lucas Meijer, Till Miltzow, Johanna Ockenfels +1
In the (Nesting) Bird Box Problem we are given a polygonal domain P and a number k and we want to know if there is a set B of k points inside P such that no two points in B can see…
Rainbow connectivity Maker-Breaker game
Juri Barkey, Bruno Borchardt, Dennis Clemens +3
We study biased Maker-Breaker games on a graph system , in which Maker's goal is to claim certain rainbow structures, i.e., specified subgraphs consisting of at…
Positional s-of-k games
Eric Duchêne, Valentin Gledel, Miloš Stojaković
We introduce a general framework for positional games in which players score points by claiming a prescribed portion of each winning set, extending the notion of scoring Maker-Brea…
Patrolling cop vs omniscient robber
Nina Chiarelli, Paul Dorbec, Miloš Stojaković +1
We study a variant of the classical Cops and Robbers game with one cop and one robber. The cop follows a fixed walk on the graph, called a patrol, that is chosen before the game be…
On constructing small subgraphs in the budget-constrained random graph process
Sylwia Antoniuk, Alberto Espuny Díaz, Kalina Petrova +1
Consider the budget-constrained random graph process introduced by Frieze, Krivelevich and Michaeli, where each time an edge is offered through the (standard) random graph process…
Maker playing against an invisible Breaker
Dennis Clemens, Fabian Hamann, Mirjana Mikalački +2
We initiate the study of the phantom version of Maker-Breaker positional games. In a phantom game, the moves of one of the players are hidden from the other player, who still has t…