Bartosz Walczak

activity

20122026

most citedTriangle-free intersection graphs of line segments with large chromatic number

67 citations · 377 across the 34 of their papers we have counts for

collaborators

46 papers

math.CO2026

Asymptotic dimension of graphs excluding an induced or fat minor

Robert Hickingbotham, Freddie Illingworth, Piotr Micek +1

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed gra…

math.CO2026

On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs

Tung Nguyen, Bartosz Walczak

A well-known problem of Erdős and Hajnal from the 1960s asks whether every graph with huge chromatic number contains a subgraph with large girth and large chromatic number. Very re…

math.CO2025★ 1 cited

Burling graphs in graphs with large chromatic number

Tara Abrishami, Marcin Briański, James Davies +4

A graph class is $χ$ -bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erdős conjectured that intersectio…

math.CO2025

A simple layered-wheel-like construction

Maria Chudnovsky, David Fischer, Sepehr Hajebi +2

In recent years, there has been significant interest in characterizing the induced subgraph obstructions to bounded treewidth and pathwidth. While this has recently been resolved f…

math.CO2024★ 1 cited

Polynomial-time recognition and maximum independent set in Burling graphs

Paweł Rzążewski, Bartosz Walczak

A Burling graph is an induced subgraph of some graph in Burling's construction of triangle-free high-chromatic graphs. Equivalently, a Burling graph is a graph that admits a so-cal…

math.CO2024★ 1 cited

Excluding a clique or a biclique in graphs of bounded induced matching treewidth

Tara Abrishami, Marcin Briański, Jadwiga Czyżewska +4

For a tree decomposition $T$ of a graph $G$ , let $μ (T)$ denote the maximum size of an induced matching in $G$ with the property that some bag of $T$ c…

cs.DS2023

Separator Theorem and Algorithms for Planar Hyperbolic Graphs

Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen +2

The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incompa…

math.CO2023

Cliquewidth and dimension

Gwenaël Joret, Piotr Micek, Michał Pilipczuk +1

We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension $k$ as a subposet. This applies in particular to…

math.CO2023★ 3 cited

Tight bound on treedepth in terms of pathwidth and longest path

Meike Hatzel, Gwenaël Joret, Piotr Micek +3

We show that every graph with pathwidth strictly less than $a$ that contains no path on $2^{b}$ vertices as a subgraph has treedepth at most $10 ab$ . The bound is best possible up to…

math.CO2022★ 15 cited

Separating polynomial $χ$ -boundedness from $χ$ -boundedness

Marcin Briański, James Davies, Bartosz Walczak

Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function $f : N \to N \cup {\infty}$ with $f (1) = 1$ and $f(n)\geq\binom…

math.CO2021

A solution to Ringel's circle problem

James Davies, Chaya Keller, Linda Kleist +2

We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to Ringel's…

math.CO2021★ 1 cited

Grounded L-graphs are polynomially $χ$ -bounded

James Davies, Tomasz Krawczyk, Rose McCarty +1

A grounded L-graph is the intersection graph of a collection of "L" shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique…

cs.CG2021

Distinguishing classes of intersection graphs of homothets or similarities of two convex disks

Mikkel Abrahamsen, Bartosz Walczak

For smooth convex disks $A$ , i.e., convex compact subsets of the plane with non-empty interior and with at most one tangent at every boundary point, we classify the classes $G^{\te…

math.CO2021

Colouring polygon visibility graphs and their generalizations

James Davies, Tomasz Krawczyk, Rose McCarty +1

Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with…

math.CO2020★ 1 cited

Degeneracy of $P_{t}$ -free and $C_{\geq t}$ -free graphs with no large complete bipartite subgraphs

Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk +3

A hereditary class of graphs $G$ is \emph{ $χ$ -bounded} if there exists a function $f$ such that every graph $G \in G$ satisfies $χ (G) \leq f (ω (G))$ , where $χ(G)…

cs.DS2020★ 11 cited

Approximating pathwidth for graphs of small treewidth

Carla Groenland, Gwenaël Joret, Wojciech Nadara +1

We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$ , approximates the pathwidth of $G$ to within a ratio of $O (t lo g t)$ . This is the first a…

cs.CG2020

Coloring and Maximum Weight Independent Set of Rectangles

Parinya Chalermsook, Bartosz Walczak

In 1960, Asplund and Grünbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an $O (ω^{2})$ -coloring, where $ω$ is the maximum size of a clique.…

math.CO2020★ 1 cited

Coloring triangle-free L-graphs with $O (lo g lo g n)$ colors

Bartosz Walczak

It is proved that triangle-free intersection graphs of $n$ L-shapes in the plane have chromatic number $O (lo g lo g n)$ . This improves the previous bound of $O (lo g n)$ (McGuinness,…

math.CO2020★ 20 cited

Clustered 3-Colouring Graphs of Bounded Degree

Vida Dujmović, Louis Esperet, Pat Morin +2

A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degr…

cs.CC2019

Subexponential-time algorithms for finding large induced sparse subgraphs

Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3

Let $C$ and $D$ be hereditary graph classes. Consider the following problem: given a graph $G \in D$ , find a largest, in terms of the number of vertices…

math.CO2019★ 25 cited

Planar graphs have bounded nonrepetitive chromatic number

Vida Dujmović, Louis Esperet, Gwenaël Joret +2

A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the se…

math.CO2018★ 3 cited

Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane

Torsten Mütze, Bartosz Walczak, Veit Wiechert

It is shown that shift graphs can be realized as disjointness graphs of 1-intersecting curves in the plane. This implies that the latter class of graphs is not $χ$ -bounded.

math.CO2017★ 10 cited

Sparse Kneser graphs are Hamiltonian

Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak

For integers $k \geq 1$ and $n \geq 2 k + 1$ , the Kneser graph $K (n, k)$ is the graph whose vertices are the $k$ -element subsets of ${1, \dots, n}$ and whose edges connect pairs of subs…

math.CO2017

Boolean dimension and local dimension

William T. Trotter, Bartosz Walczak

Dimension is a standard and well-studied measure of complexity of posets. Recent research has provided many new upper bounds on the dimension for various structurally restricted cl…