Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
 
    informatyka analityczna  
UJ coat of arms
Algorithmics Research Group abacus
 
 

Piotr Micek

PhD

phone: (+48-12) 664 75 94
fax: (+48-12) 664 66 72
email: email
office: ul. Łojasiewicza 6, 30-348 Kraków
room: 3151
 
personal homepage
 
msc thesis:[pdf]
phd thesis:[pdf]
photo

research interests
combinatorics
graphs
partially ordered sets
algorithms, approximations and on-line algorithms
discrete geometry

selected publications
  • Adam Gągol, Gwenaël Joret, Jakub Kozik and Piotr Micek,
    Pathwidth and nonrepetitive list coloring,
    manuscript
  • Adam Gągol, Piotr Micek and Bartosz Walczak,
    Graph sharing game and the structure of weighted graphs with forbidden subdivision, [arXiv]
    submitted
  • Stefan Felsner, Piotr Micek and Torsten Ueckerdt,
    On-line coloring between two lines, [arXiv]
    to be presented at SoCG 2015
  • Gwenaël Joret, Piotr Micek, William T. Trotter, Ruidong Wang and Veit Wiechert
    On the dimension of posets with cover graphs of treewidth 2, [arXiv]
    presented at SIAM Conference on Discrete Mathematics 2014
    submitted
  • Steven Chaplick, Piotr Micek, Torsten Ueckerdt, and Veit Weichert,
    A note on concurrent graph sharing games, [arXiv]
    submitted
  • Piotr Micek and Veit Wiechert,
    An on-line competitive algorithm for coloring bipartite graphs without long induced paths, [arXiv]
    preliminary version (An on-line competitive algorithm for coloring P_8-free bipartite graphs) in: Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, 516--527 (2014)
    full version submitted
  • Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, Ruidong Wang,
    Tree-width and dimension, [arXiv]
    to appear in Combinatorica
  • Grzegorz Gutowski, Jakub Kozik, Piotr Micek and Xuding Zhu,
    Lower bounds for on-line graph colorings, [arXiv]
    in: Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, 507--515 (2014)
  • Piotr Micek and Rom Pinchasi
    On the number of edges in families of pseudo-discs, [arXiv]
    unpublished manuscript
  • Michał Lasoń, Piotr Micek, Arkadiusz Pawlik and Bartosz Walczak,
    Coloring intersection graphs of arc-connected sets in the plane, [arXiv]
    presented at EuroComb 2013
    Discrete & Computational Geometry 52 (2014), Issue 2 , 399--415
  • Michał Lasoń, Piotr Micek, Noah Streib, William T. Trotter and Bartosz Walczak
    An extremal problem on crossing vectors, [arXiv]
    Journal of Combinatorial Theory, Series A 128 (2014), 41-55
  • Jean Cardinal, Kolja Knauer, Piotr Micek, and Torsten Ueckerdt
    Making octants colorful, and related covering decomposition problems, [arXiv]
    preliminary version in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 1424-1432
    full version: SIAM J. Discrete Mathematics 28-4 (2014), pp. 1948-1959
  • Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter and Bartosz Walczak,
    Triangle-free intersection graphs of line segments with large chromatic number, [arXiv]
    Journal of Combinatorial Theory, Series B 105 (2014), 6--10
  • Jean Cardinal, Kolja Knauer, Piotr Micek and Torsten Ueckerdt,
    Making triangles colorful,
    Journal of Computational Geometry 4 (2013), No 1, 240--246
  • Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter and Bartosz Walczak,
    Triangle-free geometric intersection graphs with large chromatic number, [arXiv]
    Discrete and Computational Geometry 50 (2013), 714--726
  • Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette, Thomas Hackl, Michael Hoffmann, Kolja Knauer, Stefan Langerman, Michał Lasoń, Piotr Micek, Günter Rote and Torsten Ueckerdt,
    Coloring hypergraphs induced by dynamic point sets and bottomless rectangles, [arXiv]
    presented in: Algorithms and Data Structures Symposium, WADS 2013,
    Lecture Notes in Computer Science 8037 (2013), 73--84
  • Jakub Kozik, Piotr Micek and Xuding Zhu,
    Towards on-line Ohba’s conjecture, [arXiv]
    European Journal of Combinatorics 36 (2014), 110--121
  • Jakub Kozik and Piotr Micek,
    Nonrepetitive choice number of trees, [arXiv]
    SIAM Journal on Discrete Mathematics 27 (2013), No. 1, 436--446
  • Bartłomiej Bosek, Kamil Kloch, Tomasz Krawczyk and Piotr Micek,
    On-line dimension of semi-orders, [pdf]
    Order 30, Issue 2 (2013) 593--615
  • Stefan Felsner, Kamil Kloch, Grzegorz Matecki and Piotr Micek,
    On-line chain partitions of up-growing semi-orders, [arXiv]
    Order 30 (2013), no. 1, 85--101
  • Kolja Knauer, Piotr Micek and Bartosz Walczak,
    Outerplanar graph drawings with few slopes, [arXiv]
    Computational Geometry: Theory and Applications 47 (2014), issue 5, 614--624
    Preliminary version in: Computing and Combinatorics (COCOON 2012), Lecture Notes in Computer Science 7434 (2012), 323-334
  • Jarosław Grytczuk, Jakub Kozik and Piotr Micek,
    A new approach to nonrepetitive sequences, [arXiv]
    Random Structures and Algorithms 42, issue 2 (2013), 214–-225
  • Bartłomiej Bosek, Kamil Kloch, Tomasz Krawczyk and Piotr Micek,
    On-line version of Rabinovitch theorem for proper intervals, [pdf]
    Discrete Mathematics 312 (2012), issue 23, 3426--3436
  • Piotr Micek and Bartosz Walczak,
    Parity in graph sharing games, [pdf]
    Discrete Mathematics 312 (2012), issue 10, 1788--1795
  • Bartłomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, Grzegorz Matecki and Piotr Micek,
    On-line chain partitions of orders: a survey, [pdf]
    Order 29 (2012), no. 1, 49--73
  • Piotr Micek and Bartosz Walczak,
    A graph-grabbing game, [pdf]
    Combinatorics, Probability and Computing 20 (2011), no. 4, 623--629
  • Kolja Knauer, Piotr Micek and Torsten Ueckerdt,
    How to eat 4/9 of a pizza, [arxiv]
    Discrete Mathematics 311 (2011), issue 16, 1635--1645
  • Patrick Baier, Bartłomiej Bosek and Piotr Micek,
    On-line Chain Partitioning of Up-growing Interval Orders, [pdf],
    Order 24 (2007), no. 1, 1--13
  • Bartłomiej Bosek and Piotr Micek,
    On-line Adaptive Chain Covering of Upgrowing Posets, [pdf],
    Discrete Mathematics and Theoretical Computer Science Proceedings AF (2006), 37-48
  • Iwona Cieślik, Marcin Kozik and Piotr Micek,
    On-line Coloring of I_s-free graphs and co-planar graphs, [pdf],
    Discrete Mathematics and Theoretical Computer Science Proceedings AF (2006), 61-68
  • Bartłomiej Bosek and Piotr Micek,
    Variants of Online Chain Partition Problem of Posets, [pdf],
    Electronic Notes in Theoretical Computer Science 140 (2005), 3-13

  • some recent collaborators 
    Jean CardinalUniversité Libre de Bruxelles
    Stefan FelsnerTechnische Universität Berlin
    Grzegorz GutowskiJagiellonian University
    Gwenaël JoretUniversité Libre de Bruxelles
    Kolja KnauerUniversité Aix-Marseille
    Jakub KozikJagiellonian University
    William T. TrotterGeorgia Institute of Technology
    Torsten UeckerdtKarlsruhe Institute of Technology
    Veit WiechertTechnische Universität Berlin
    Xuding ZhuZhejiang Normal University

    grants
    2007 - 2008 On-line Coloring of Intervals, Interval Orders and Interval Graphs
      Ministry of Science and Higher Education
      N206 2728 33
    2010 - 2012 On-line algorithms and combinatorial games
      Ministry of Science and Higher Education
      N206 4923 38
    2010 - 2012 Movement tracking in monitored zones
      Ministry of Science and Higher Education
      R00 0081 11
    2011 - 2014 Graph drawings and representations
      Ministry of Science and Higher Education
      as a part of EUROCORES program: Graphs in Geometry and Algorithms (EuroGIGA), maintained by European Science Foundation
    2011 - 2014 Algorithmic Local Lovász Lemma as double counting
      Polish National Science Center
      2011/01/D/ST1/04412
    2012 - 2015 On-line choosability
      Polish National Science Center
      UMO-2011/03/D/ST6/01370
    2013 - 2015 Coloring intersection graphs of geometric objects in the plane
      Ministry of Science and Higher Education
      grant within Mobility Plus program

    short cv
    2004M.Sc. in Computer ScienceJagiellonian UniversityKraków, Poland
    2008Ph.D. in Mathematical SciencesJagiellonian UniversityKraków, Poland
    2008-11assistant professorJagiellonian UniversityKraków, Poland
    2011research fellow (three months)Zhejiang Normal UniversityJinhua, China
    2011-associate professorJagiellonian UniversityKraków, Poland
    2013-research fellow (18 months)Technische Universität BerlinBerlin, Germany
     
     
      webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl