9 papers
On multidimensional generalization of binary search
Dariusz Dereniowski, Przemysław Gordinowicz, Karolina Wróbel
This work generalizes the binary search problem to a -dimensional domain , where and , in the following way. Giv…
The polynomial method for 3-path extendability of list colourings of planar graphs
Przemysław Gordinowicz, Paweł Twardowski
We restate Thomassen's theorem of 3-extendability, an extension of the famous planar 5-choosability theorem, in terms of graph polynomials. This yields an Alon--Tarsi equivalent of…
Edge and Pair Queries -- Random Graphs and Complexity
Dariusz Dereniowski, Przemysław Gordinowicz, Paweł Prałat
We investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random gr…
The polynomial method for list-colouring extendability of outerplanar graphs
Przemysław Gordinowicz, Paweł Twardowski
We restate theorems of Hutchinson on list-colouring extendability for outerplanar graphs in terms of non-vanishing monomials in a graph polynomial, which yields an Alon-Tarsi equiv…
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…