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

Showing 2020Show all

5 papers · 1 filter

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…