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

Tomasz Krawczyk

PhD

phone: (+48-12) 664 75 66
fax: (+48-12) 664 66 72
email: email
office: ul. Łojasiewicza 6, 30-348 Kraków
room: 3149
office hours: Tuesday 12:00 - 14:00
 
personal homepage
for students
 
photo

research interests
on-line algorithms
combinatorics on graphs and posets
combinatorial games
discrete geometry

selected publications
  • Bartłomiej Bosek, Hal Kierstead, Tomasz Krawczyk, Grzegorz Matecki, Matthew E. Smith
    An Improved Subexponential Bound for On-line Chain Partitioning [arxiv]
  • Bartłomiej Bosek, Tomasz Krawczyk
    A subexponential upper bound for the on-line chain partitioning problem
    [to appear in Combinatorica]
  • Tomasz Krawczyk, Bartosz Walczak
    Coloring relatives of interval overlap graphs via on-line games [arxiv]
    ICALP 2014 (track A), Lecture Notes in Computer Science 8572, pp. 738-750, 2014
  • Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, Bartosz Walczak
    Triangle-free intersection graphs of line segments with large chromatic number [arxiv]
    Journal of Combinatorial Theory, Series B, 105 (2014), 6-10,
  • Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, Bartosz Walczak
    Triangle-free geometric intersection graphs with large chromatic number [arxiv]
    Discrete & Computational Geometry, Volume 50, Issue 3, pp 714-726, 2013
  • Bartłomiej Bosek, Kamil Kloch, Tomasz Krawczyk, Piotr Micek
    On-line dimension of semi-orders
    Order, Volume 30, Issue 2, pp. 593-615, 2013
  • Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak
    Coloring triangle-free rectangular frame intersection graphs with O(log log n) colors [arxiv]
    WG 2013, Lecture Notes in Computer Science 8165, pp. 333-344 (2013)
  • Bartłomiej Bosek, Tomasz Krawczyk, Grzegorz Matecki
    First-Fit coloring of incomparability graphs
    SIAM Journal on Discrete Mathematics, Volume 27, Issue 1, pp. 126-140, 2013
  • Stefan Felsner, Tomasz Krawczyk, William T. Trotter
    On-line dimension for posets excluding two long incomparable chains
    Order, Volume 30, Issue 1, pp. 1-12, 2013
  • Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak
    Extending partial representations of function graphs and permutation graphs [arxiv]
    ESA 2012, Lecture Notes in Computer Science 7501, pp. 671-682, 2012
  • Bartłomiej Bosek, Kamil Kloch, Tomasz Krawczyk, Piotr Micek
    On-line version of Rabinovitch theorem for proper intervals
    Discrete Mathematics 312, Issue 23, pp. 3426-3436, 2012
  • Bartłomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, Grzegorz Matecki, Piotr Micek
    On-line chain partitions of orders: a survey
    Order, Volume 29, Issue 1, pp. 49-73, 2012
  • Bartłomiej Bosek, Tomasz Krawczyk, Grzegorz Matecki
    Forbidden structures for efficient First-Fit chain partitioning (extended abstract)
    EuroComb 2011, Electronic Notes in Discrete Mathematics, Volume 38, pp. 173–179, 2011
  • Bartłomiej Bosek, Tomasz Krawczyk
    The sub-exponential upper bound for on-line chain partitioning problem
    Proceedings of the 51st Symposium on Foundations of Computer Science, FOCS10, pp. 347-354, 2010
  • Bartłomiej Bosek, Tomasz Krawczyk, Edward Szczypka
    First-Fit algorithm for the on-line chain partitioning problem
    SIAM Journal on Discrete Mathematics, Volume 23, Issue 4, pp. 1992-1999, 2010
  • Wit Foryś, Tomasz Krawczyk
    An algorithmic approach to the problem of a semiretract base
    Theoretical Computer Science, Volume 369, pp. 314 – 322, 2006
  • Wit Foryś, Tomasz Krawczyk
    An automaton that recognizes the base of a semretract
    Procedings of the 5th International Conference on Words, Words 2005, pp. 235-248, 2005
  • Wit Foryś, Tomasz Krawczyk, James Anderson
    Semiretracts – a counterexample and some results
    Theoretical Computer Science, Volume 307, pp. 117-127, 2003

  • grants
    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
    2012 - 2014 Coloring games on graphs and partially ordered sets
      Polish National Science Center
      MO-2011/03/B/ST6/01367

    short cv
    2000MSc (computer science)Jagiellonian UniversityKraków, Poland
    2005PhDJagiellonian UniversityKraków, Poland
     
     
      webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl