Publikacje

• A simple layered-wheel-like construction - 2026
  Electronic Journal of Combinatorics 33 (2026), P3.52 Maria Chudnovsky, David Fischer, Sepehr Hajebi, Sophie Spirkl, Bartosz Walczak
• A solution to Ringel's circle problem - 2026
  Journal of the European Mathematical Society 28 (2026), 4873-4892 James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
• Cliquewidth and dimension - 2026
  Proceedings of the London Mathematical Society 132 (2026), e70116 Gwenaël Joret, Piotr Micek, Michał Pilipczuk, Bartosz Walczak
• Burling graphs in graphs with large chromatic number - 2026 ACM/SIAM Symposium on Discrete Algorithms [SODA], (2026), 3978-3998 Tara Abrishami, Marcin Briański, James Davies, Xiying Du, Jana Masaříková, Paweł Rzążewski, Bartosz Walczak
• On a clique game and the Erdős-Hajnal problem on high-chromatic high-girth subgraphs - 2026 ACM/SIAM Symposium on Discrete Algorithms [SODA], (2026), 2903-2927 Seth Pettie, Gábor Tardos, Bartosz Walczak
• Polynomial-time recognition and maximum independent set in Burling graphs - 2026 International Workshop on Graph-Theoretic Concepts in Computer Science [WG] 16124 of Lecture Notes in Computer Science (2026), 445-460 Paweł Rzążewski, Bartosz Walczak
• Excluding a clique or a biclique in graphs of bounded induced matching treewidth - 2025
  SIAM Journal on Discrete Mathematics 39 (2025), 1189-1200 Tara Abrishami, Marcin Briański, Jadwiga Czyżewska, Rose McCarty, Martin Milanič, Paweł Rzążewski, Bartosz Walczak
• Separator theorem and algorithms for planar hyperbolic graphs - 2024 International Symposium on Computational Geometry [SoCG] 293 of Leibniz International Proceedings in Informatics (LIPIcs) (2024), 67:1-67:17 Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, Karol Węgrzycki
• Tight bound on treedepth in terms of pathwidth and longest path - 2024
  Combinatorica 44 (2024), 417-427 Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
• Coloring triangle-free L-graphs with O(log log n) colors - 2024
  European Journal of Combinatorics 117 (2024), 103831 Bartosz Walczak
• Cliquewidth and dimension - 2024 ACM/SIAM Symposium on Discrete Algorithms [SODA], (2024), 1437-1446 Gwenaël Joret, Piotr Micek, Michał Pilipczuk, Bartosz Walczak
• Separating polynomial χ-boundedness from χ-boundedness - 2024
  Combinatorica 44 (2024), 1-8 Marcin Briański, James Davies, Bartosz Walczak
• Grounded L-graphs are polynomially χ-bounded - 2023
  Discrete and Computational Geometry 70 (2023), 1523-1550 James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
• Distinguishing classes of intersection graphs of homothets or similarities of two convex disks - 2023 International Symposium on Computational Geometry [SoCG] 258 of Leibniz International Proceedings in Informatics (LIPIcs) (2023), 2:1-2:16 Mikkel Abrahamsen, Bartosz Walczak
• Coloring polygon visibility graphs and their generalizations - 2023
  Journal of Combinatorial Theory. Series B 161 (2023), 268-300 James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
• Approximating pathwidth for graphs of small treewidth - 2023
  ACM Transactions on Algorithms 19 (2023), 16:1-19 Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak
• A solution to Ringel's circle problem - 2022 International Symposium on Computational Geometry [SoCG] 224 of Leibniz International Proceedings in Informatics (LIPIcs) (2022), 33:1-33:14 James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
• Clustered 3-colouring graphs of bounded degree - 2022
  Combinatorics Probability and Computing 31 (2022), 123-135 Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, David R. Wood
• Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs - 2022
  Journal of Combinatorial Theory. Series B 152 (2022), 353-378 Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
• Subexponential-time algorithms for finding large induced sparse subgraphs - 2021
  Algorithmica 83 (2021), 2634-2650 Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
• Sparse Kneser graphs are Hamiltonian - 2021
  Journal of the London Mathematical Society 103 (2021), 1253-1275 Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
• Colouring polygon visibility graphs and their generalizations - 2021 International Symposium on Computational Geometry [SoCG] 189 of Leibniz International Proceedings in Informatics (LIPIcs) (2021), 29:1-29:16 James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
• Approximating pathwidth for graphs of small treewidth - 2021 ACM/SIAM Symposium on Discrete Algorithms [SODA], (2021), 1965-1976 Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak
• Coloring and maximum weight independent set of rectangles - 2021 ACM/SIAM Symposium on Discrete Algorithms [SODA], (2021), 860-868 Parinya Chalermsook, Bartosz Walczak
• Planar graphs have bounded nonrepetitive chromatic number - 2020
  Advances in Combinatorics 2020 (2020), 5:1-11 Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood
• Subexponential-time algorithms for finding large induced sparse subgraphs - 2019 vol. 148 of Leibniz International Proceedings in Informatics (2019), "14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany", Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
• Outerstring graphs are χ-bounded - 2019
  SIAM Journal on Discrete Mathematics 33 (2019), 2181-2199 Alexandre Rok, Bartosz Walczak
• Coloring triangle-free L-graphs with O(log log n) colors - 2019
  Acta Mathematica Universitatis Comenianae 88 (2019), 1063-1069 Bartosz Walczak
• Coloring curves that cross a fixed curve - 2019
  Discrete and Computational Geometry 61 (2019), 830-851 Alexandre Rok, Bartosz Walczak
• Dimension of posets with planar cover graphs excluding two long incomparable chains - 2019
  Journal of Combinatorial Theory - Series A 164 (2019), 1-23 David M. Howard, Noah Streib, William T. Trotter, Bartosz Walczak, Ruidong Wang
• Common tangents of two disjoint polygons in linear time and constant workspace - 2018
  ACM Transactions on Algorithms 15 (2018), 12:1-21 Mikkel Abrahamsen, Bartosz Walczak
• Sparse Kneser graphs are Hamiltonian - 2018 (2018), "Proceedings of 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC’18)", Association for Computing Machinery (ACM) Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
• Dimension and cut vertices: an application of Ramsey theory - 2018 (2018), "Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham", Cambridge University Press William T. Trotter, Bartosz Walczak, Ruidong Wang
• Boolean dimension and local dimension - 2017 vol. 61 of Electronic Notes in Discrete Mathematics (2017), "The Ninth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2017", Elsevier Science William T. Trotter, Bartosz Walczak
• On-line approach to off-line coloring problems on graphs with geometric representations - 2017
  Combinatorica 37 (2017), 1139-1179 Tomasz Krawczyk, Bartosz Walczak
• Extending partial representations of trapezoid graphs - 2017 vol. 10520 of Lecture Notes in Computer Science (2017), "Graph-Theoretic Concepts in Computer Science, 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers", Springer Tomasz Krawczyk, Bartosz Walczak
• Coloring curves that cross a fixed curve - 2017 vol. 77 of Leibniz International Proceedings in Informatics (2017), "33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia", Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandre Rok, Bartosz Walczak
• Graph sharing game and the structure of weighted graphs with a forbidden subdivision - 2017
  Journal of Graph Theory 85 (2017), 22-50 Adam Gągol, Piotr Micek, Bartosz Walczak
• On the Beer index of convexity and its variants - 2017
  Discrete and Computational Geometry 57 (2017), 179-214 Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak
• Minors and dimension - 2017
  Journal of Combinatorial Theory. Series B 122 (2017), 668-689 Bartosz Walczak
• Outer common tangents and nesting of convex hulls in linear time and constant workspace - 2016 vol. 57 of Leibniz International Proceedings in Informatics (2016), "24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark", Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikkel Abrahamsen, Bartosz Walczak
• Graph drawings with one bend and few slopes - 2016 vol. 9644 of Lecture Notes in Computer Science (2016), "LATIN 2016: Theoretical Informatics, 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings", Springer Kolja Knauer, Bartosz Walczak
• Decomposition of multiple packings with subquadratic union complexity - 2016
  Combinatorics Probability and Computing 25 (2016), 145-153 János Pach, Bartosz Walczak
• Tree-width and dimension - 2016
  Combinatorica 36 (2016), 431-450 Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, Ruidong Wang
• Asymmetric coloring games on incomparability graphs - 2015 vol. 49 of Electronic Notes in Discrete Mathematics (2015), "The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015", Elsevier Science Tomasz Krawczyk, Bartosz Walczak
• New bounds on the maximum number of edges in k-quasi-planar graphs - 2015
  Computational Geometry: Theory and Applications 50 (2015), 24-33 Andrew Suk, Bartosz Walczak
• On the Beer index of convexity and its variants - 2015 vol. 34 of Leibniz International Proceedings in Informatics (2015), "31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands", Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak
• Minors and dimension - 2015 (2015), "26th Annual ACM-SIAM Symposium on Discrete Algorithms, January 4-6, 2015, San Diego, California, USA", Society for Industrial and Applied Mathematics (SIAM) Bartosz Walczak
• Triangle-free geometric intersection graphs with no large independent sets - 2015
  Discrete and Computational Geometry 53 (2015), 221-225 Bartosz Walczak
• Coloring triangle-free rectangle overlap graphs with O(log log n) colors - 2015
  Discrete and Computational Geometry 53 (2015), 199-220 Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak
• Coloring intersection graphs of arc-connected sets in the plane - 2014
  Discrete and Computational Geometry 52 (2014), 399-415 Michał Lasoń, Piotr Micek, Arkadiusz Pawlik, Bartosz Walczak
• An extremal problem on crossing vectors - 2014
  Journal of Combinatorial Theory - Series A 128 (2014), 41-55 Michał Lasoń, Piotr Micek, Noah Streib, William T. Trotter, Bartosz Walczak
• Coloring relatives of interval overlap graphs via on-line games - 2014
  Lecture Notes in Computer Science vol. 8572 of (2014), "Automata, Languages, and Programming, 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I", Springer Tomasz Krawczyk, Bartosz Walczak
• Outerstring graphs are χ-bounded - 2014 (2014), "30th Annual Symposium on Computational Geometry, SoCG 2014, June 8-11, 2014, Kyoto, Japan", Association for Computing Machinery (ACM) Alexandre Rok, Bartosz Walczak
• Triangle-free intersection graphs of line segments with large chromatic number - 2014
  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
• Outerplanar graph drawings with few slopes - 2014
  Computational Geometry: Theory and Applications 47 (2014), 614-624 Kolja Knauer, Piotr Micek, Bartosz Walczak
• New bounds on the maximum number of edges in k-quasi-planar graphs - 2013
  Lecture Notes in Computer Science vol. 8242 of (2013), "Graph Drawing, 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers", Springer Andrew Suk, Bartosz Walczak
• Coloring triangle-free rectangular frame intersection graphs with O(log log n) colors - 2013
  Lecture Notes in Computer Science vol. 8165 of (2013), "Graph-Theoretic Concepts in Computer Science, 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers", Springer Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak
• Coloring intersection graphs of arcwise connected sets in the plane - 2013
  Crm Series vol. 16 of CRM Series (2013), "The Seventh European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013", Springer Michał Lasoń, Piotr Micek, Arkadiusz Pawlik, Bartosz Walczak
• Triangle-free geometric intersection graphs with large chromatic number - 2013
  Discrete and Computational Geometry 50 (2013), 714-726 Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, Bartosz Walczak
• Extending partial representations of function graphs and permutation graphs - 2012
  Lecture Notes in Computer Science vol. 7501 of (2012), "Algorithms – ESA 2012, 20th Annual European Symposium on Algorithms, Ljubljana, Slovenia, September 10-12, 2012, Proceedings", Springer Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak
• Outerplanar graph drawings with few slopes - 2012
  Lecture Notes in Computer Science vol. 7434 of (2012), "Computing and Combinatorics, 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012, Proceedings", Springer Kolja Knauer, Piotr Micek, Bartosz Walczak
• Parity in graph sharing games - 2012
  Discrete Mathematics 312 (2012), 1788-1795 Piotr Micek, Bartosz Walczak
• A graph-grabbing game - 2011
  Combinatorics Probability and Computing 20 (2011), 623-629 Piotr Micek, Bartosz Walczak
• A simple representation of subwords of the Fibonacci word - 2010
  Information Processing Letters 110 (2010), 956-960 Bartosz Walczak