Bartosz Walczak
dr hab.
phone (+48) 12 664 75 92
fax (+48) 12 664 66 72
email
address ul. prof. S. Łojasiewicza 6, 30-348 Kraków
room 3067

Research Interests

  • Graph theory
  • Algorithms
  • Discrete geometry

Papers

Mikkel Abrahamsen, Bartosz Walczak
Distinguishing classes of intersection graphs of homothets or similarities of two convex disks 39th International Symposium on Computational Geometry, SoCG 2023, Leibniz International Proceedings in Informatics (LIPIcs) 258, 2:1–16, 2023
James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
Coloring polygon visibility graphs and their generalizations Journal of Combinatorial Theory, Series B 161, 268–300, 2023; preliminary version in: 37th International Symposium on Computational Geometry, SoCG 2021, Leibniz International Proceedings in Informatics (LIPIcs) 189, 29:1–16, 2021
Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak
Approximating pathwidth for graphs of small treewidth ACM Transactions on Algorithms 19, 16:1–19, 2023; preliminary version in: 32nd Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2021, 1965–1976, 2021
James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
A solution to Ringel's circle problem 38th International Symposium on Computational Geometry, SoCG 2022, Leibniz International Proceedings in Informatics (LIPIcs) 224, 33:1–14, 2022
Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, David R. Wood
Clustered 3-colouring graphs of bounded degree Combinatorics, Probability and Computing 31, 123–135, 2022
Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs Journal of Combinatorial Theory, Series B 152, 353–378, 2022
Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
Subexponential-time algorithms for finding large induced sparse subgraphs Algorithmica 83, 2634–2650, 2021; preliminary version in: 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Leibniz International Proceedings in Informatics (LIPIcs) 148, 23:1–11, 2019
Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
Sparse Kneser graphs are Hamiltonian Journal of the London Mathematical Society 103, 1253–1275, 2021; preliminary version in: 50th Annual ACM SIGACT Symposium on the Theory of Computing, STOC 2018, 912–919, 2018
Parinya Chalermsook, Bartosz Walczak
Coloring and maximum weight independent set of rectangles 32nd Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2021, 860–868, 2021
Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood
Planar graphs have bounded nonrepetitive chromatic number Advances in Combinatorics 2020, 5:1–11, 2020
Alexandre Rok, Bartosz Walczak
Outerstring graphs are χ-bounded SIAM Journal on Discrete Mathematics 33, 2181–2199, 2019; preliminary version in: 30th Annual Symposium on Computational Geometry, SoCG 2014, 136–143, 2014
Alexandre Rok, Bartosz Walczak
Coloring curves that cross a fixed curve Discrete and Computational Geometry 61, 830–851, 2019; preliminary version in: 33rd International Symposium on Computational Geometry, SoCG 2017, Leibniz International Proceedings in Informatics (LIPIcs) 77, 56:1–15, 2017
David M. Howard, Noah Streib, William T. Trotter, Bartosz Walczak, Ruidong Wang
Dimension of posets with planar cover graphs excluding two long incomparable chains Journal of Combinatorial Theory, Series A 164, 1–23, 2019
Mikkel Abrahamsen, Bartosz Walczak
Common tangents of two disjoint polygons in linear time and constant workspace ACM Transactions on Algorithms 15, 12:1–21, 2018; preliminary version: Outer common tangents and nesting of convex hulls in linear time and constant workspace, 24th Annual European Symposium on Algorithms, ESA 2016, Leibniz International Proceedings in Informatics (LIPIcs) 57, 4:1–15, 2016
William T. Trotter, Bartosz Walczak, Ruidong Wang
Dimension and cut vertices: an application of Ramsey theory Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham, 187–199, 2018
Tomasz Krawczyk, Bartosz Walczak
On-line approach to off-line coloring problems on graphs with geometric representations Combinatorica 37, 1139–1179, 2017; preliminary version: Coloring relatives of interval overlap graphs via on-line games, 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014, Lecture Notes in Computer Science 8572, 738–750, 2014
Tomasz Krawczyk, Bartosz Walczak
Extending partial representations of trapezoid graphs 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, Lecture Notes in Computer Science 10520, 358–371, 2017
Adam Gągol, Piotr Micek, Bartosz Walczak
Graph sharing game and the structure of weighted graphs with a forbidden subdivision Journal of Graph Theory 85, 22–50, 2017
Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak
On the Beer index of convexity and its variants Discrete and Computational Geometry 57, 179–214, 2017; preliminary version in: 31st International Symposium on Computational Geometry, SoCG 2015, Leibniz International Proceedings in Informatics (LIPIcs) 34, 406–420, 2015
Bartosz Walczak
Minors and dimension Journal of Combinatorial Theory, Series B 122, 668–689, 2017; preliminary version in: 26th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2015, 1698–1707, 2015
Kolja Knauer, Bartosz Walczak
Graph drawings with one bend and few slopes 12th Latin American Symposium on Theoretical Informatics, LATIN 2016, Lecture Notes in Computer Science 9644, 549–561, 2016
János Pach, Bartosz Walczak
Decomposition of multiple packings with subquadratic union complexity Combinatorics, Probability and Computing 25, 145–153, 2016
Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, Ruidong Wang
Tree-width and dimension Combinatorica 36, 431–450, 2016
Andrew Suk, Bartosz Walczak
New bounds on the maximum number of edges in k-quasi-planar graphs Computational Geometry: Theory and Applications 50, 24–33, 2015; preliminary version in: 21st International Symposium on Graph Drawing, GD 2013, Lecture Notes in Computer Science 8242, 95–106, 2013
Bartosz Walczak
Triangle-free geometric intersection graphs with no large independent sets Discrete and Computational Geometry 53, 221–225, 2015
Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak
Coloring triangle-free rectangle overlap graphs with O(log log n) colors Discrete and Computational Geometry 53, 199–220, 2015; preliminary version: Coloring triangle-free rectangular frame intersection graphs with O(log log n) colors, 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, Lecture Notes in Computer Science 8165, 333–344, 2013
Michał Lasoń, Piotr Micek, Arkadiusz Pawlik, Bartosz Walczak
Coloring intersection graphs of arc-connected sets in the plane Discrete and Computational Geometry 52, 399–415, 2014
Michał Lasoń, Piotr Micek, Noah Streib, William T. Trotter, Bartosz Walczak
An extremal problem on crossing vectors Journal of Combinatorial Theory, Series A 128, 41–55, 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 Journal of Combinatorial Theory, Series B 105, 6–10, 2014
Kolja Knauer, Piotr Micek, Bartosz Walczak
Outerplanar graph drawings with few slopes Computational Geometry: Theory and Applications 47, 614–624, 2014; preliminary version in: 18th Annual International Conference on Computing and Combinatorics, COCOON 2012, Lecture Notes in Computer Science 7434, 323–334, 2012
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, Bartosz Walczak
Triangle-free geometric intersection graphs with large chromatic number Discrete and Computational Geometry 50, 714–726, 2013
Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak
Extending partial representations of function graphs and permutation graphs 20th Annual European Symposium on Algorithms, ESA 2012, Lecture Notes in Computer Science 7501, 671–682, 2012
Piotr Micek, Bartosz Walczak
Parity in graph sharing games Discrete Mathematics 312, 1788–1795, 2012
Piotr Micek, Bartosz Walczak
A graph-grabbing game Combinatorics, Probability and Computing 20, 623–629, 2011
Bartosz Walczak
A simple representation of subwords of the Fibonacci word Information Processing Letters 110, 956–960, 2010

Short CV

2008 MSc (computer science) Uniwersytet Jagielloński Kraków, Poland
2012 PhD (computer science) Uniwersytet Jagielloński Kraków, Poland
2013–2014 Postdoctoral fellowship (12 months) École Polytechnique Fédérale de Lausanne Lausanne, Switzerland
2014 "Mobilność Plus" research fellowship (6 months) Univerzita Karlova v Praze Praha, Czechia
2014–2015 Visiting assistant professor (9 months) Georgia Institute of Technology Atlanta, USA
2017 Habilitation (computer science) Uniwersytet Jagielloński Kraków, Poland
2017–2018 Gastprofessor (6 months) Technische Universität Berlin Berlin, Germany