Piotr Micek
I am a 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.
You might see or have seen me:
2nd Adriatic Workshop on Graphs and Probability,
Brac 06/2023 
Geometry & Graphs,
Barbados 02/2023 
9th Polish Combinatorial Conference, Będlewo 09/2022 
Order & Geometry Workshop,
Ciążeń 09/2022 
Structural Graph Theory Workshop,
Gułtowy 06/2022 
1st Adriatic Workshop on Graphs and Probability,
Hvar 06/2023 
Geometry & Graphs,
Barbados 01/2022 
Graph Theory Workshop, Oberwolfach 01/2022 
Graph Product Structure Theory Workshop,
Banff 11/2021 
Sparsity in Algorithms, Combinatorics and Logic,
Dagstuhl Seminar 09/2021 
...
Papers
As of Jan 24, 2024. Conference and journal versions merged.
Here is my Google Scholar profile.

Boolean dimension of a Boolean lattice
with
Marcin Briański,
Jędrzej Hodor
,
Hoang La, and
Katzper Michno
submitted

Product structure extension of the AlonSeymourThomas theorem
with
Marc Distel,
Vida Dujmović,
David Eppstein,
Robert Hickingbotham,
Gwenaël Joret,
Pat Morin,
Michał Seweryn, and
David R. Wood
submitted

Boundeddegree planar graphs do not have boundeddegree product structure
with
Vida Dujmović,
Gwenaël Joret,
Pat Morin, and
David R. Wood
submitted

Boolean dimension and dimboundedness: Planar cover graph with a zero
with
Heather S. Blake, 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
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
SIAM Journal on Discrete Mathematics (SIDMA) 28 (4): 19481959, 2014
preliminary version: (SODA 2014) Proceedings of the 25th Annual ACMSIAM Symposium on Discrete Algorithms 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
Combinatorica, 38/5: 11291148, 2018.
preliminary version: (SODA 2016) Proceedings of the 27th Annual ACMSIAM Symposium on Discrete Algorithms 18041813, 2016.

Burling graphs, chromatic number, and orthogonal treedecompositions
with
Stefan Felsner,
Gwenaël Joret,
William T. Trotter, and
Veit Wiechert
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.

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 R. Wood
Combinatorica 40, 839–868, 2020.

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

ErdősHajnal properties for powers of sparse graphs
with
Marcin Briański,
Michał Pilipczuk,
Michał T. Seweryn
SIAM Journal on Discrete Mathematics (SIDMA): 35, no. 1, 447464, 2021

Excluding a ladder
with
Tony Huynh,
Gwenaël Joret,
Michał T. Seweryn,
Paul Wollan
Combinatorica 42, 405–432, 2022.

Reconfiguring independent sets on interval graphs
with
Marcin Briański,
Stefan Felsner, and
Jędrzej Hodor
46th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2021.

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

Tight bounds on the clique chromatic number
with
Bruce Reed,
Gwenaël Joret, and
Michiel Smid
Electronic Journal of Combinatorics (EJC) Vol. 28, Issue 3, 2021.

Adjacency labelling for planar graphs (and beyond)
[video]
with
Vida Dujmović,
Louis Esperet,
Cyril Gavoille,
Gwenaël Joret, and
Pat Morin
Journal of the ACM (J.ACM) Vol. 68, Issue 6, Article 42, 2021
preliminary version:
(FOCS 2020) IEEE 61st Annual Symposium on Foundations of Computer Science, 577588, 2020.

Improved bounds for weak coloring numbers
with
Gwenaël Joret
Electronic Journal of Combinatorics (EJC) Vol. 29, Issue 1, 2022.

Colouring bottomless rectangles and arborescences
with
Jean Cardinal,
Kolja Knauer,
Dömötör Pálvölgyi,
Torsten Ueckerdt, and
Narmada Varadarajan
Computational Geometry vol. 115, 2023

Treedepth vs circumference
with
Marcin Briański,
Gwenaël Joret,
Konrad Majewski,
Michał T. Seweryn,
Roohani Sharma
Combinatorica vol. 43, 659664, 2023

The excluded tree minor theorem revisited
with
Vida Dujmović,
Robert Hickingbotham,
Gwenaël Joret,
Pat Morin, and
David R. Wood
Combinatorics, Probability and Computing, 33, 8590, 2024.

Tight bound on treedepth in terms of pathwidth and longest path
with
Meike Hatzel,
Gwenaël Joret,
Marcin Pilipczuk,
Torsten Ueckerdt, and
Bartosz Walczak
Combinatorica, 2023

Dimension is polynomial in height for posets with planar cover graphs
with
Jakub Kozik and
William T. Trotter
Journal of Combinatorial Theory, Series B (JCTB) vol. 165, 164196, 2024

Cliquewidth and dimension
with
Gwenaël Joret,
Michał Pilipczuk, and
Bartosz Walczak
extended abstract: to appear in (SODA 2024) Proceedings of the 2024 ACMSIAM Symposium on Discrete Algorithms 14371446

The gridminor theorem revisited
with
Vida Dujmović,
Robert Hickingbotham,
Jędrzej Hodor,
Gwenaël Joret,
Hoang La,
Pat Morin,
Clément Rambaud, and
David R. Wood
extended abstract: (SODA 2024) Proceedings of the 2024 ACMSIAM Symposium on Discrete Algorithms 12411245
other unpublished manuscripts