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 Nov 6, 2024. Conference and journal versions merged.
Here is my Google Scholar profile.
  1. 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
  2. On-line coloring of Is-free graphs and co-planar 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
  3. On-line 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
  4. On-line chain partitioning of up-growing interval orders
    with Patrick Baier and Bartłomiej Bosek
    Order (ORDE): 24.1, pp. 1–13, 2007
  5. A graph-grabbing game
    with Bartosz Walczak
    Combinatorics, Probability & Computing (CPC): 20.4, 623–629, 2011
  6. How to eat 4/9 of a pizza
    with Kolja Knauer, and Torsten Ueckerdt
    Discrete Mathematics (DM): 311.16, 1635–1645, 2011
  7. Parity in graph sharing games
    with Bartosz Walczak
    Discrete Mathematics (DM): 312.10, 1788–1795, 2012
  8. On-line version of Rabinovitch theorem for proper intervals
    with Bartłomiej Bosek, Kamil Kloch, and Tomasz Krawczyk
    Discrete Mathematics (DM): 312.23, 3426–3436, 2012
  9. On-line chain partitions of orders: a survey
    with Bartłomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, and Grzegorz Matecki
    Order (ORDE): 29.1, 49-73, 2012
  10. On-line chain partitions of up-growing semi-orders
    with Stefan Felsner, Kamil Kloch, and Grzegorz Matecki
    Order (ORDE): 30.1,85–101, 2013
  11. Making triangles colorful
    with Jean Cardinal, Kolja Knauer, and Torsten Ueckerdt
    Journal of Computational Geometry: 4.1, 240–246, 2013
  12. On-line dimension of semi-orders
    with Bartłomiej Bosek, Kamil Kloch, and Tomasz Krawczyk
    Order (ORDE): 30.2, 593–615, 2013
  13. 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, 73-84, 2013
  14. Triangle-free 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 , 714-726, 2013
  15. Nonrepetitive choice number of trees
    with Jakub Kozik
    SIAM Journal on Discrete Mathematics (SIDMA): 27, no. 1, 436-446, 2013
  16. A new approach to nonrepetitive sequences
    with Jarosław Grytczuk and Jakub Kozik
    Random Structures and Algorithms (RSA): 42, Issue 2, 214-225, 2013
  17. Coloring intersection graphs of arc-connected sets in the plane
    with Michał Lasoń, Arkadiusz Pawlik, and Bartosz Walczak
    final version: Discrete & Computational Geometry (DCG): 52, Issue 2, 399-415, 2014
    preliminary version: 7th European Conference on Combinatorics, Graph Theory and Applications (EuroComb'13): vol. 16 of CRM Series, 299-304, 2013
  18. Towards an on-line version of Ohba’s conjecture
    with Jakub Kozik, and Xuding Zhu
    European Journal of Combinatorics (EJC): 36, 110-121, 2014
  19. Outerplanar graph drawings with few slopes
    with Kolja Knauer, Bartosz Walczak
    final version: Computational Geometry: Theory and Applications (CGTA): 47 (5), 614-624, 2014
    preliminary version: Computing and combinatorics. Lecture Notes in Comput. Sci.: vol. 7434, 2012
  20. Lower bounds for on-line graph colorings
    with Grzegorz Gutowski, Jakub Kozik and Xuding Zhu
    Algorithms and Computation: 25th International Symposium (ISAAC) Proceedings: 507-515, 2014
  21. An on-line competitive algorithm for coloring bipartite graphs without long induced paths
    with Veit Wiechert
    Algorithmica (ALGO) 77, 1060-1070, 2017.
    preliminary version: An on-line competitive algorithm for coloring P8-free bipartite graphs, Algorithms and Computation: 25th International Symposium (ISAAC) Proceedings: 516-527, 2014
  22. An extremal problem on crossing vectors
    with Michał Lasoń, Noah Streib, William T. Trotter, and Bartosz Walczak
    Journal of Combinatorial Theory, Series A (JCT-A): 128, 41–55, 2014
  23. Triangle-free 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 (JCT-B), 105: 6-10, 2014.
  24. Making octants colorful, and related covering decomposition problems
    with Jean Cardinal, Kolja Knauer, and Torsten Ueckerdt
    SIAM Journal on Discrete Mathematics (SIDMA) 28 (4): 1948-1959, 2014
    preliminary version: (SODA 2014) Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms 1424-1432, 2014
  25. On-line coloring between two lines
    with Stefan Felsner and Torsten Ueckerdt
    31st International Symposium on Computational Geometry (SoCG), LIPIcs 34: 630-641, 2015
  26. A note on concurrent graph sharing games
    with Steven Chaplick, Torsten Ueckerdt, and Veit Wiechert
    Integers 16, No. G1, 2016.
  27. Pathwidth and nonrepetitive list colorings
    with Adam Gągol, Gwenaël Joret, and Jakub Kozik
    Electronic Journal of Combinatorics (E-JC) Vol. 23, Issue 4, 2016.
  28. Tree-width and dimension
    with Gwenaël Joret, Kevin G. Milans, William T. Trotter, Bartosz Walczak, and Ruidong Wang
    Combinatorica, 36/4:431-450, 2016.
  29. 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:185-234, 2017
  30. 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:22-50, 2017
  31. Topological minors of cover graphs and dimension
    with Veit Wiechert
    Journal of Graph Theory (JGT) 86.3:295–314, 2017
  32. Sparsity and dimension
    with Gwenaël Joret and Veit Wiechert
    Combinatorica, 38/5: 1129-1148, 2018.
    preliminary version: (SODA 2016) Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms 1804-1813, 2016.
  33. Burling graphs, chromatic number, and orthogonal tree-decompositions
    with Stefan Felsner, Gwenaël Joret, William T. Trotter, and Veit Wiechert
    Electronic Journal of Combinatorics (E-JC) 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.
  34. On an extremal problem for poset dimension
    with Grzegorz Guśpiel and Adam Polak
    Order (ORDE) 35: 489-493, 2018.
  35. 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), 2754-2790, 2017.
  36. The queue-number of posets of bounded width or height
    with Kolja Knauer and Torsten Ueckerdt
    26th International Symposium, Graph Drawing (GD) 2018, Barcelona, Spain, September 26-28, 2018, Proceedings
    Graph Drawing and Network Visualization, 200-212, 2018.
  37. Nowhere dense graph classes and dimension
    with Gwenaël Joret, Patrice Ossona de Mendez, and Veit Wiechert
    Combinatorica 39(5): 1055-1079, 2019.
  38. Separating tree-chromatic number from path-chromatic number
    with Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros, Heather Smith, Libby Taylor, and William T. Trotter
    Journal of Combinatorial Theory, Series B (JCT-B), 138: 206-218, 2019.
  39. 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, 172-177, 2019.
  40. Boolean dimension, components and blocks
    with Tamás Mészáros and William T. Trotter
    Order (ORDE) 37, 287-298, 2020.
  41. Boolean dimension and tree-width
    with Stefan Felsner and Tamás Mészáros
    Combinatorica 40, 655-677, 2020.
  42. Seymour's conjecture on 2-connected graphs of large pathwidth
    with Tony Huynh, Gwenaël Joret, and David R. Wood
    Combinatorica 40, 839–868, 2020.
  43. Planar graphs have bounded queue-number [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 862-875, 2019.
  44. Erdős-Hajnal properties for powers of sparse graphs
    with Marcin Briański, Michał Pilipczuk, Michał T. Seweryn
    SIAM Journal on Discrete Mathematics (SIDMA): 35, no. 1, 447-464, 2021
  45. Excluding a ladder
    with Tony Huynh, Gwenaël Joret, Michał T. Seweryn, Paul Wollan
    Combinatorica 42, 405–432, 2022.
  46. 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.
  47. 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 ACM-SIAM Symposium on Discrete Algorithms 2212--2226, 2020.
  48. Tight bounds on the clique chromatic number
    with Bruce Reed, Gwenaël Joret, and Michiel Smid
    Electronic Journal of Combinatorics (E-JC) Vol. 28, Issue 3, 2021.
  49. 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, 577-588, 2020.
  50. Improved bounds for weak coloring numbers
    with Gwenaël Joret
    Electronic Journal of Combinatorics (E-JC) Vol. 29, Issue 1, 2022.
  51. 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
  52. Treedepth vs circumference
    with Marcin Briański, Gwenaël Joret, Konrad Majewski, Michał T. Seweryn, Roohani Sharma
    Combinatorica vol. 43, 659-664, 2023
  53. 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, 85-90, 2024.
  54. 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
  55. Dimension is polynomial in height for posets with planar cover graphs
    with Jakub Kozik and William T. Trotter
    Journal of Combinatorial Theory, Series B (JCT-B) vol. 165, 164--196, 2024
  56. Cliquewidth and dimension
    with Gwenaël Joret, Michał Pilipczuk, and Bartosz Walczak
    extended abstract: (SODA 2024) Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms 1437-1446
  57. The grid-minor 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 ACM-SIAM Symposium on Discrete Algorithms 1241-1245
  58. Boolean dimension of a Boolean lattice
    with Marcin Briański, Jędrzej Hodor , Hoang La, and Katzper Michno
    Order (online first), 2024.
  59. Bounded-degree planar graphs do not have bounded-degree product structure
    with Vida Dujmović, Gwenaël Joret, Pat Morin, and David R. Wood
    Electronic Journal of Combinatorics (E-JC) Vol. 31, Issue 2, 2024.
  60. Planar graphs in blowups of fans
    with Vida Dujmović, Gwenaël Joret, Pat Morin, and David R. Wood
    accepted to (SODA 2025) Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms
  61. Weak coloring numbers of minor-closed graph classes
    with Jędrzej Hodor, Hoang La, and Clément Rambaud
    accepted to (SODA 2025) Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms

other unpublished manuscripts

Affiliations

Research Interests

Some Collaborators

PhD students

MSc students

BSc students

My recent talks and lectures

Funding

My Events

flags counting since December 2013

Free counters!