21 citations · 42 across the 14 of their papers we have counts for
6 papers · 1 filter
The Maker-Breaker Largest Connected Subgraph Game
Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney +2
Given a graph and , we introduce the following game played in . Each round, Alice colours an uncoloured vertex of red, and then Bob colours one blue (i…
Redicolouring digraphs: directed treewidth and cycle-degeneracy
Nicolas Nisse, Lucas Picasarri-Arrieta, Ignasi Sau
Given a digraph on vertices and a vertex , the cycle-degree of is the minimum size of a set intersecting every directed…
Problems, proofs, and disproofs on the inversion number
Guillaume Aubian, Frédéric Havet, Florian Hörsch +4
The {\it inversion} of a set of vertices in a digraph consists in reversing the direction of all arcs of . The {\it inversion number} of an oriented grap…
Centroidal localization game
Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk +3
One important problem in a network is to locate an (invisible) moving entity by using distance-detectors placed at strategical locations. For instance, the metric dimension of a gr…
Localization game on geometric and planar graphs
Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk +3
The main topic of this paper is motivated by a localization problem in cellular networks. Given a graph we want to localize a walking agent by checking his distance to as few v…
Subdivisions of oriented cycles in digraphs with large chromatic number
Nathann Cohen, Frédéric Havet, William Lochet +1
An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle , there are digraphs containing no subdivision of (as a subdigraph) and…