Piotr Micek
I am an associate professor at
Jagiellonian University
Faculty of Mathematics and Computer Science
Theoretical Computer Science Department
reach me:
firstname.lastname@gmail.com
+48126647594
find me:
room 3151, Faculty of Math and Computer Science
This is my Berlin's website. I spent some years in Berlin and this website became the main place where I collect my stuff.
Upcoming event
You might see or have seen me:
Structural Graph Theory Workshop,
Gułtowy 06/2020 
Seymour is 70,
Lyon 06/2020 
School on Graph Theory,
Murol 06/2020 
Sparsity in Algorithms, Combinatorics and Logic, Dagstuhl 03/2020 
Geometry & Graphs,
Barbados 02/2020 
Structural Graph Theory Workshop,
Gułtowy 06/2019 
CzechSlovak GRAPHS,
High Tatras 06/2019 
CanaDAM,
Vanvouver 05/2019 
Geometry & Graphs,
Barbados 03/2019 
Southeastern,
Boca Raton 03/2019 
Graph Theory,
Oberwolfach 01/2019 
7th Polish Combinatorial Conference 09/2018 
Order & Geometry Workshop 09/2018 
Order & Geometry Fall School 09/2018 
SWgraphs, Karlsruhe, 08/2018 
ICGT, Lyon, 07/2018  ...
Papers
As of January 10, 2021. Conference and journal versions merged.
Here is my Google Scholar profile.

ErdősHajnal properties for powers of sparse graphs
with
Marcin Briański,
Michał Pilipczuk,
Michał Seweryn
submitted

Tight bounds on the clique chromatic number
with
Bruce Reed,
Gwenaël Joret, and
Michiel Smid
submitted

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
with
Marthe Bonamy,
Oscar Defrain, and
Lhouari Nourine
manuscript

Excluding a ladder
with
Tony Huynh,
Gwenaël Joret,
Michał T. Seweryn,
Paul Wollan
submitted

Planar cubic graphs have small diameter
with
Kolja Knauer
manuscript

Colouring bottomless rectangles and arborescences
with
Jean Cardinal,
Kolja Knauer,
Dömötör Pálvölgyi,
Torsten Ueckerdt, and
Narmada Varadarajan
submitted

Dimension is polynomial in height for posets with planar cover graphs
with
Jakub Kozik and
William T. Trotter
submitted

Variants of online chain partition problem of posets
with
Bartłomiej Bosek
Proceedings of Computational Logic and Applications, CLA 2004,
Electronic Notes on Theoretical Computer Science: 140, 3–13, 2005

Online coloring of Isfree graphs and coplanar graphs
with
Iwona Cieślik and
Marcin Kozik
Proceedings of Computational logic and applications, CLA 2005,
Discrete Mathematics & Theoretical Computer Science Proceedings, AF., 61–68, 2006

Online adaptive chain covering of upgrowing posets
with
Bartłomiej Bosek
Proceedings of Computational Logic and Applications, CLA 2005,
Discrete Mathematics & Theoretical Computer Science Proceedings, AF., 37–48, 2006

Online chain partitioning of upgrowing interval orders
with
Patrick Baier and
Bartłomiej Bosek
Order (ORDE): 24.1, pp. 1–13, 2007

A graphgrabbing game
with
Bartosz Walczak
Combinatorics, Probability & Computing (CPC): 20.4, 623–629, 2011

How to eat 4/9 of a pizza
with
Kolja Knauer, and
Torsten Ueckerdt
Discrete Mathematics (DM): 311.16, 1635–1645, 2011

Parity in graph sharing games
with
Bartosz Walczak
Discrete Mathematics (DM): 312.10, 1788–1795, 2012

Online version of Rabinovitch theorem for proper intervals
with
Bartłomiej Bosek,
Kamil Kloch, and
Tomasz Krawczyk
Discrete Mathematics (DM): 312.23, 3426–3436, 2012

Online chain partitions of orders: a survey
with
Bartłomiej Bosek,
Stefan Felsner,
Kamil Kloch,
Tomasz Krawczyk, and
Grzegorz Matecki
Order (ORDE): 29.1, 4973, 2012

Online chain partitions of upgrowing semiorders
with
Stefan Felsner,
Kamil Kloch, and
Grzegorz Matecki
Order (ORDE): 30.1,85–101, 2013

Making triangles colorful
with
Jean Cardinal,
Kolja Knauer, and
Torsten Ueckerdt
Journal of Computational Geometry: 4.1, 240–246, 2013

Online dimension of semiorders
with
Bartłomiej Bosek,
Kamil Kloch, and
Tomasz Krawczyk
Order (ORDE): 30.2, 593–615, 2013

Coloring hypergraphs induced by dynamic point sets and bottomless rectangles
with
Andrei Asinowski,
Jean Cardinal,
Nathann Cohen,
Sébastien Collette,
Thomas Hackl,
Michael Hoffmann,
Kolja Knauer,
Stefan Langerman,
Michał Lasoń,
Günter Rote, and
Torsten Ueckerdt
Proc. Workshop on Algorithms and Data Structures (WADS), Algorithms and data structures, Lecture Notes in Computer Science: 8037, 7384, 2013

Trianglefree geometric intersection graphs with large chromatic number
with Arkadiusz Pawlik,
Jakub Kozik,
Tomasz Krawczyk,
Michał Lasoń,
William T. Trotter, and
Bartosz Walczak
Discrete & Computational Geometry (DCG): 50 , 714726, 2013

Nonrepetitive choice number of trees
with Jakub Kozik
SIAM Journal on Discrete Mathematics (SIDMA): 27, no. 1, 436446, 2013

A new approach to nonrepetitive sequences
with Jarosław Grytczuk and
Jakub Kozik
Random Structures and Algorithms (RSA): 42, Issue 2, 214225, 2013

Coloring intersection graphs of arcconnected sets in the plane
with Michał Lasoń,
Arkadiusz Pawlik, and
Bartosz Walczak
final version:
Discrete & Computational Geometry (DCG): 52, Issue 2, 399415, 2014
preliminary version:
7th European Conference on Combinatorics, Graph Theory and Applications (EuroComb'13): vol. 16 of CRM Series, 299304, 2013

Towards an online version of Ohba’s conjecture
with Jakub Kozik, and
Xuding Zhu
European Journal of Combinatorics (EJC): 36, 110121, 2014

Outerplanar graph drawings with few slopes
with Kolja Knauer,
Bartosz Walczak
final version: Computational Geometry: Theory and Applications (CGTA): 47 (5), 614624, 2014
preliminary version: Computing and combinatorics. Lecture Notes in Comput. Sci.: vol. 7434, 2012

Lower bounds for online graph colorings
with
Grzegorz Gutowski,
Jakub Kozik
and
Xuding Zhu
Algorithms and Computation: 25th International Symposium (ISAAC) Proceedings: 507515, 2014

An online competitive algorithm for coloring bipartite graphs without long induced paths
with
Veit Wiechert
full version: Algorithmica (ALGO) 77, 10601070, 2017.
preliminary version: An online competitive algorithm for coloring P8free bipartite graphs,
Algorithms and Computation: 25th International Symposium (ISAAC) Proceedings: 516527, 2014

An extremal problem on crossing vectors
with Michał Lasoń,
Noah Streib,
William T. Trotter, and
Bartosz Walczak
Journal of Combinatorial Theory, Series A (JCTA): 128, 41–55, 2014

Trianglefree intersection graphs of line segments with large chromatic number
with
Arkadiusz Pawlik,
Jakub Kozik,
Tomasz Krawczyk,
Michał Lasoń,
William T. Trotter, and
Bartosz Walczak
Journal of Combinatorial Theory, Series B (JCTB), 105: 610, 2014.

Making octants colorful, and related covering decomposition problems
with
Jean Cardinal,
Kolja Knauer, and
Torsten Ueckerdt
full version: SIAM Journal on Discrete Mathematics (SIDMA) 28 (4): 19481959, 2014
preliminary version: Proceedings of the 25th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'14): 14241432, 2014

Online coloring between two lines
with
Stefan Felsner
and
Torsten Ueckerdt
31st International Symposium on Computational Geometry (SoCG),
LIPIcs 34: 630641, 2015

A note on concurrent graph sharing games
with
Steven Chaplick,
Torsten Ueckerdt, and
Veit Wiechert
Integers 16, No. G1, 2016.

Pathwidth and nonrepetitive list colorings
with Adam Gągol,
Gwenaël Joret, and
Jakub Kozik
Electronic Journal of Combinatorics (EJC) Vol. 23, Issue 4, 2016.

Treewidth and dimension
with
Gwenaël Joret,
Kevin G. Milans,
William T. Trotter,
Bartosz Walczak, and
Ruidong Wang
Combinatorica, 36/4:431450, 2016.

On the dimension of posets with cover graphs of treewidth 2
with
Gwenaël Joret,
William T. Trotter,
Ruidong Wang, and
Veit Wiechert
Order (ORDE) 34.2:185234, 2017

Graph sharing game and the structure of weighted graphs with a forbidden subdivision
with Adam Gągol and
Bartosz Walczak
Journal of Graph Theory (JGT) 85.1:2250, 2017

Topological minors of cover graphs and dimension
with
Veit Wiechert
Journal of Graph Theory (JGT) 86.3:295–314, 2017

Sparsity and dimension
with
Gwenaël Joret
and
Veit Wiechert
full version: Combinatorica, 38/5: 11291148, 2018.
preliminary version: Proceedings of the 27th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'16): 18041813, 2016.

Burling graphs, chromatic number, and orthogonal treedecompositions
with
Stefan Felsner,
Gwenaël Joret,
William T. Trotter, and
Veit Wiechert
full version: Electronic Journal of Combinatorics (EJC) 25(1), 2018.
extended abstract:
Electronic Notes in Discrete Mathematics 61 (2017). The European Conference
on Combinatorics, Graph Theory and Applications (EuroComb’17):415–420.

On an extremal problem for poset dimension
with
Grzegorz Guśpiel and
Adam Polak
Order (ORDE) 35: 489493, 2018.

Planar posets have dimension at most linear in their height
with
Gwenaël Joret and
Veit Wiechert
SIAM Journal on Discrete Mathematics (SIDMA) 31(4), 27542790, 2017.

The queuenumber of posets of bounded width or height
with
Kolja Knauer and
Torsten Ueckerdt
26th International Symposium, Graph Drawing (GD) 2018, Barcelona, Spain, September 2628, 2018, Proceedings
Graph Drawing and Network Visualization, 200212, 2018.

Nowhere dense graph classes and dimension
with
Gwenaël Joret,
Patrice Ossona de Mendez, and
Veit Wiechert
Combinatorica 39(5): 10551079, 2019.

Separating treechromatic number from pathchromatic number
with
Fidel BarreraCruz,
Stefan Felsner,
Tamás Mészáros,
Heather Smith,
Libby Taylor, and
William T. Trotter
Journal of Combinatorial Theory, Series B (JCTB), 138: 206218, 2019.

A Note on the Minimum Number of Edges in Hypergraphs with Property O
with
Gal Kronenberg,
Christopher Kusch,
Ander Lamaison,
and
Tuan Tran
European Journal of Combinatorics 81, 172177, 2019.

Boolean dimension, components and blocks
with
Tamás Mészáros and
William T. Trotter
Order (ORDE) 37, 287298, 2020.

Improved bounds for centered colorings
with
Michał Dębski,
Stefan Felsner and
Felix Schröder
full version: submitted
preliminary version: Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms (SODA):
22122226, 2020.

Boolean dimension and treewidth
with
Stefan Felsner and
Tamás Mészáros
Combinatorica 40, 655677, 2020.

Seymour's conjecture on 2connected graphs of large pathwidth
with
Tony Huynh,
Gwenaël Joret, and
David Wood
in print, Combinatorica, 2021.

Planar graphs have bounded queuenumber
[video]
with
Vida Dujmović,
Gwenaël Joret,
Pat Morin,
Torsten Ueckerdt, and
David Wood
full version:
Journal of the ACM (J.ACM) 67, 4, Article 22, 2020.
preliminary version:
the 60th Annual Symposium on Foundations of Computer Science (FOCS), 862875, 2019.

Adjacency labelling for planar graphs (and beyond)
[video]
with
Vida Dujmović,
Louis Esperet,
Cyril Gavoille,
Gwenaël Joret, and
Pat Morin
full version: accepted to Journal of the ACM (J.ACM)
preliminary version:
the 61th Annual Symposium on Foundations of Computer Science (FOCS) 2020.
other unpublished manuscripts