73 citations · 427 across the 49 of their papers we have counts for
5 papers · 2 filters
Graph sharing game and the structure of weighted graphs with a forbidden subdivision
Adam Gągol, Piotr Micek, Bartosz Walczak
In the graph sharing game, two players share a connected graph with non-negative weights assigned to the vertices, claiming and collecting the vertices of one by one, while…
A note on concurrent graph sharing games
Steven Chaplick, Piotr Micek, Torsten Ueckerdt +1
In the concurrent graph sharing game, two players, called First and Second, share the vertices of a connected graph with positive vertex-weights summing up to as follows. The g…
On-line coloring between two lines
Stefan Felsner, Piotr Micek, Torsten Ueckerdt
We study on-line colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the rep…
On the dimension of posets with cover graphs of treewidth
Gwenaël Joret, Piotr Micek, William T. Trotter +2
In 1977, Trotter and Moore proved that a poset has dimension at most whenever its cover graph is a forest, or equivalently, has treewidth at most . On the other hand, a well…
Lower bounds for on-line graph colorings
Grzegorz Gutowski, Jakub Kozik, Piotr Micek +1
We propose two strategies for Presenter in on-line graph coloring games. The first one constructs bipartite graphs and forces any on-line coloring algorithm to use …