Bartosz Walczak

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 52

Top Topics

Independent Set

Computationally Challenging

Top Venues

Discret. Comput. Geom.

Publications

Bartosz Walczak
Coloring triangle-free L-graphs with O(loglogn) colors. Eur. J. Comb. 117 (2024)
Sándor Kisfaludi-Bak, Jana Masaríková, Erik Jan van Leeuwen, Bartosz Walczak, Karol Wegrzycki
Separator Theorem and Algorithms for Planar Hyperbolic Graphs. SoCG (2024)
Gwenaël Joret, Piotr Micek, Michal Pilipczuk, Bartosz Walczak
Cliquewidth and Dimension. SODA (2024)
Pawel Rzazewski, Bartosz Walczak
Polynomial-time recognition and maximum independent set in Burling graphs. CoRR (2024)
Marcin Brianski, James Davies, Bartosz Walczak
Separating Polynomial χ-Boundedness from χ-Boundedness. Comb. 44 (1) (2024)
Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
Tight Bound on Treedepth in Terms of Pathwidth and Longest Path. Comb. 44 (2) (2024)
James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
Coloring polygon visibility graphs and their generalizations. J. Comb. Theory, Ser. B 161 (2023)
James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
Grounded L-Graphs Are Polynomially χ-Bounded. Discret. Comput. Geom. 70 (4) (2023)
Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
Tight bound on treedepth in terms of pathwidth and longest path. CoRR (2023)
Mikkel Abrahamsen, Bartosz Walczak
Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. SoCG (2023)
Sándor Kisfaludi-Bak, Jana Masarikova, Erik Jan van Leeuwen, Bartosz Walczak, Karol Wegrzycki
Separator Theorem and Algorithms for Planar Hyperbolic Graphs. CoRR (2023)
Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak
Approximating Pathwidth for Graphs of Small Treewidth. ACM Trans. Algorithms 19 (2) (2023)
Gwenaël Joret, Piotr Micek, Michal Pilipczuk, Bartosz Walczak
Cliquewidth and dimension. CoRR (2023)
James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
A Solution to Ringel's Circle Problem. SoCG (2022)
Marthe Bonamy, Nicolas Bousquet, Michal Pilipczuk, Pawel Rzazewski, Stéphan Thomassé, Bartosz Walczak
-free graphs with no large complete bipartite subgraphs. J. Comb. Theory, Ser. B 152 (2022)
Marcin Brianski, James Davies, Bartosz Walczak
Separating polynomial χ-boundedness from χ-boundedness. CoRR (2022)
Vida Dujmovic, Louis Esperet, Pat Morin, Bartosz Walczak, David R. Wood
Clustered 3-colouring graphs of bounded degree. Comb. Probab. Comput. 31 (1) (2022)
James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
Colouring Polygon Visibility Graphs and Their Generalizations. SoCG (2021)
James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
Colouring polygon visibility graphs and their generalizations. CoRR (2021)
Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak
Approximating Pathwidth for Graphs of Small Treewidth. SODA (2021)
James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
A solution to Ringel's circle problem. CoRR (2021)
Jana Novotná, Karolina Okrasa, Michal Pilipczuk, Pawel Rzazewski, Erik Jan van Leeuwen, Bartosz Walczak
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. Algorithmica 83 (8) (2021)
Mikkel Abrahamsen, Bartosz Walczak
Distinguishing classes of intersection graphs of homothets or similarities of two convex disks. CoRR (2021)
James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
Grounded L-graphs are polynomially χ-bounded. CoRR (2021)
Parinya Chalermsook, Bartosz Walczak
Coloring and Maximum Weight Independent Set of Rectangles. SODA (2021)
Parinya Chalermsook, Bartosz Walczak
Coloring and Maximum Weight Independent Set of Rectangles. CoRR (2020)
Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak
Approximating pathwidth for graphs of small treewidth. CoRR (2020)
Bartosz Walczak
Coloring triangle-free L-graphs with O(log log n) colors. CoRR (2020)
Jana Novotná, Karolina Okrasa, Michal Pilipczuk, Pawel Rzazewski, Erik Jan van Leeuwen, Bartosz Walczak
Subexponential-time algorithms for finding large induced sparse subgraphs. CoRR (2019)
Jana Novotná, Karolina Okrasa, Michal Pilipczuk, Pawel Rzazewski, Erik Jan van Leeuwen, Bartosz Walczak
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. IPEC (2019)
Alexandre Rok, Bartosz Walczak
Outerstring Graphs are χ-Bounded. SIAM J. Discret. Math. 33 (4) (2019)
Alexandre Rok, Bartosz Walczak
Coloring Curves that Cross a Fixed Curve. Discret. Comput. Geom. 61 (4) (2019)
David M. Howard, Noah Streib, William T. Trotter, Bartosz Walczak, Ruidong Wang
Dimension of posets with planar cover graphs excluding two long incomparable chains. J. Comb. Theory, Ser. A 164 (2019)
Vida Dujmovic, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood
Planar graphs have bounded nonrepetitive chromatic number. CoRR (2019)
Mikkel Abrahamsen, Bartosz Walczak
Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace. ACM Trans. Algorithms 15 (1) (2019)
Torsten Mütze, Bartosz Walczak, Veit Wiechert
Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane. CoRR (2018)
Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
Sparse Kneser graphs are Hamiltonian. STOC (2018)
Tomasz Krawczyk, Bartosz Walczak
Extending Partial Representations of Trapezoid Graphs. WG (2017)
Tomasz Krawczyk, Bartosz Walczak
On-Line Approach to Off-Line Coloring Problems on Graphs with Geometric Representations. Comb. 37 (6) (2017)
William T. Trotter, Bartosz Walczak
Boolean dimension and local dimension. CoRR (2017)
Bartosz Walczak
Minors and dimension. J. Comb. Theory, Ser. B 122 (2017)
Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak
On the Beer Index of Convexity and Its Variants. Discret. Comput. Geom. 57 (1) (2017)
Alexandre Rok, Bartosz Walczak
Coloring Curves That Cross a Fixed Curve. SoCG (2017)
Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
Sparse Kneser graphs are Hamiltonian. CoRR (2017)
Adam Gagol, Piotr Micek, Bartosz Walczak
Graph Sharing Game and the Structure of Weighted Graphs with a Forbidden Subdivision. J. Graph Theory 85 (1) (2017)
William T. Trotter, Bartosz Walczak
Boolean Dimension and Local Dimension. Electron. Notes Discret. Math. 61 (2017)
David M. Howard, Noah Streib, William T. Trotter, Bartosz Walczak, Ruidong Wang
The dimension of posets with planar cover graphs excluding two long incomparable chains. CoRR (2016)
Mikkel Abrahamsen, Bartosz Walczak
Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace. ESA (2016)
Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, Ruidong Wang
Tree-width and dimension. Comb. 36 (4) (2016)
János Pach, Bartosz Walczak
Decomposition of Multiple Packings with Subquadratic Union Complexity. Comb. Probab. Comput. 25 (1) (2016)
Kolja Knauer, Bartosz Walczak
Graph Drawings with One Bend and Few Slopes. LATIN (2016)
Mikkel Abrahamsen, Bartosz Walczak
Outer common tangents and nesting of convex hulls of two disjoint simple polygons in linear time and constant workspace. CoRR (2016)
Tomasz Krawczyk, Bartosz Walczak
Asymmetric Coloring Games on Incomparability Graphs. Electron. Notes Discret. Math. 49 (2015)
Tomasz Krawczyk, Bartosz Walczak
Asymmetric coloring games on incomparability graphs. CoRR (2015)
Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak
Coloring Triangle-Free Rectangle Overlap Graphs with $$O(\log \log n)$$ O ( log log n ) Colors. Discret. Comput. Geom. 53 (1) (2015)
Bartosz Walczak
Minors and Dimension. SODA (2015)
Kolja B. Knauer, Bartosz Walczak
Graph drawings with one bend and few slopes. CoRR (2015)
Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak
On the Beer Index of Convexity and Its Variants. SoCG (2015)
Bartosz Walczak
Triangle-Free Geometric Intersection Graphs with No Large Independent Sets. Discret. Comput. Geom. 53 (1) (2015)
Andrew Suk, Bartosz Walczak
New bounds on the maximum number of edges in k-quasi-planar graphs. Comput. Geom. 50 (2015)
Alexandre Rok, Bartosz Walczak
Coloring curves intersecting a fixed line. CoRR (2015)
William T. Trotter, Bartosz Walczak, Ruidong Wang
Dimension and cut vertices: an application of Ramsey theory. CoRR (2015)
Michal Lason, Piotr Micek, Arkadiusz Pawlik, Bartosz Walczak
Coloring Intersection Graphs of Arc-Connected Sets in the Plane. Discret. Comput. Geom. 52 (2) (2014)
Adam Gagol, Piotr Micek, Bartosz Walczak
Graph sharing game and the structure of weighted graphs with forbidden subdivision. CoRR (2014)
Bartosz Walczak
Triangle-free geometric intersection graphs with no big independent sets. CoRR (2014)
Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak
On the Beer index of convexity and its variants. CoRR (2014)
Alexandre Rok, Bartosz Walczak
Outerstring graphs are χ-bounded. SoCG (2014)
Michal Lason, Piotr Micek, Noah Streib, William T. Trotter, Bartosz Walczak
An extremal problem on crossing vectors. J. Comb. Theory, Ser. A 128 (2014)
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michal Lason, Piotr Micek, William T. Trotter, Bartosz Walczak
Triangle-free intersection graphs of line segments with large chromatic number. J. Comb. Theory, Ser. B 105 (2014)
Tomasz Krawczyk, Bartosz Walczak
Coloring Relatives of Interval Overlap Graphs via On-line Games. ICALP (1) (2014)
Tomasz Krawczyk, Bartosz Walczak
Coloring relatives of interval overlap graphs via on-line games. CoRR (2014)
Kolja B. Knauer, Piotr Micek, Bartosz Walczak
Outerplanar graph drawings with few slopes. Comput. Geom. 47 (5) (2014)
Bartosz Walczak
Minors and dimension. CoRR (2014)
Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak
Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(loglogn) Colors. WG (2013)
Andrew Suk, Bartosz Walczak
New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs. Graph Drawing (2013)
Andrew Suk, Bartosz Walczak
New bounds on the maximum number of edges in k-quasi-planar graphs. CoRR (2013)
János Pach, Bartosz Walczak
Decomposition of multiple packings with subquadratic union complexity. CoRR (2013)
Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, Ruidong Wang
Tree-Width and Dimension CoRR (2013)
Alexandre Rok, Bartosz Walczak
Outerstring graphs are $χ$-bounded. CoRR (2013)
Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak
Coloring triangle-free rectangular frame intersection graphs with O(log log n) colors CoRR (2013)
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michal Lason, Piotr Micek, William T. Trotter, Bartosz Walczak
Triangle-Free Geometric Intersection Graphs with Large Chromatic Number. Discret. Comput. Geom. 50 (3) (2013)
Michal Lason, Piotr Micek, Arkadiusz Pawlik, Bartosz Walczak
Coloring intersection graphs of arc-connected sets in the plane. CoRR (2013)
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michal Lason, Piotr Micek, William T. Trotter, Bartosz Walczak
Triangle-free intersection graphs of line segments with large chromatic number CoRR (2012)
Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak
Extending partial representations of function graphs and permutation graphs CoRR (2012)
Michal Lason, Piotr Micek, Noah Streib, William T. Trotter, Bartosz Walczak
An extremal problem on crossing vectors CoRR (2012)
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michal Lason, Piotr Micek, William T. Trotter, Bartosz Walczak
Triangle-free geometric intersection graphs with large chromatic number CoRR (2012)
Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak
Extending Partial Representations of Function Graphs and Permutation Graphs. ESA (2012)
Kolja B. Knauer, Piotr Micek, Bartosz Walczak
Outerplanar Graph Drawings with Few Slopes. COCOON (2012)
Kolja B. Knauer, Piotr Micek, Bartosz Walczak
Outerplanar graph drawings with few slopes CoRR (2012)
Piotr Micek, Bartosz Walczak
Parity in graph sharing games. Discret. Math. 312 (10) (2012)
Piotr Micek, Bartosz Walczak
A Graph-Grabbing Game. Comb. Probab. Comput. 20 (4) (2011)
Bartosz Walczak
A simple representation of subwords of the Fibonacci word. Inf. Process. Lett. 110 (21) (2010)