21 citations · 61 across the 11 of their papers we have counts for
13 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…
Dense free subgroups of automorphism groups of homogeneous partially ordered sets
Szymon Głąb, Przemysław Gordinowicz, Filip Strobin
A countable poset is ultrahomogeneous if every isomorphism between its finite subposets can be extended to an automorphism. The groups of such posets ha…
The 2-surviving rate of planar graphs with average degree lower than
Przemysław Gordinowicz
Let be any connected graph on vertices, Let be any positive integer. Suppose that a fire breaks out at some vertex of Then, in each turn firefighters ca…
Cops and Robbers on Intersection Graphs
Tomáš Gavenčiak, Przemysław Gordinowicz, Vít Jelínek +2
The cop number of a graph is the smallest such that cops win the game of cops and robber on . We investigate the maximum cop number of geometric intersection graphs,…
Cops and Robbers ordinals of cop-win trees
Anthony Bonato, Przemysław Gordinowicz, Gena Hahn
A relational characterization of cop-win graphs was provided by Nowakowski and Winkler in their seminal paper on the game of Cops and Robbers. As a by-product of that characterizat…
Planar graph is on fire
Przemysław Gordinowicz
Let be any connected graph on vertices, Let be any positive integer. Suppose that a fire breaks out on some vertex of Then in each turn firefighters…
The capture time of the hypercube
Anthony Bonato, William B. Kinnersley, P. Gordinowicz +1
In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the captu…
The robber strikes back
Anthony Bonato, Stephen Finbow, Przemyslaw Gordinowicz +5
We consider the new game of Cops and Attacking Robbers, which is identical to the usual Cops and Robbers game except that if the robber moves to a vertex containing a single cop, t…