Zobrazeno 1 - 10
of 177
pro vyhledávání: '"Walczak, Bartosz"'
Autor:
Rzążewski, Paweł, Walczak, Bartosz
A Burling graph is an induced subgraph of some graph in Burling's construction of triangle-free high-chromatic graphs. We provide a polynomial-time algorithm which decides whether a given graph is a Burling graph and if it is, constructs its intersec
Externí odkaz:
http://arxiv.org/abs/2407.16666
Autor:
Abrishami, Tara, Briański, Marcin, Czyżewska, Jadwiga, McCarty, Rose, Milanič, Martin, Rzążewski, Paweł, Walczak, Bartosz
When $\mathcal{T}$ is a tree decomposition of a graph $G$, we write $\mu(\mathcal{T})$ for the maximum size of an induced matching in $G$ all of whose edges intersect one bag of $\mathcal{T}$. The induced matching treewidth of a graph $G$ is the mini
Externí odkaz:
http://arxiv.org/abs/2405.04617
Autor:
Kisfaludi-Bak, Sándor, Masaříková, Jana, van Leeuwen, Erik Jan, Walczak, Bartosz, Węgrzycki, Karol
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 incomparable. Motivated by the broad study of algorithms and separators on pl
Externí odkaz:
http://arxiv.org/abs/2310.11283
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 posets whose cover graphs have bounded treewidth, as the cliquewidth
Externí odkaz:
http://arxiv.org/abs/2308.11950
Autor:
Hatzel, Meike, Joret, Gwenaël, Micek, Piotr, Pilipczuk, Marcin, Ueckerdt, Torsten, Walczak, Bartosz
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 $10ab$. The bound is best possible up to a constant factor.
Comment: v3: corrected some typos. v2: revised
Comment: v3: corrected some typos. v2: revised
Externí odkaz:
http://arxiv.org/abs/2302.02995
Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function $f\colon\mathbb{N}\to\mathbb{N}\cup\{\infty\}$ with $f(1)=1$ and $f(n)\geq\binom{3n+1}{3}$, we construct a hereditary class of graphs $\mathcal{G}$ su
Externí odkaz:
http://arxiv.org/abs/2201.08814
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 circle problem (1959). The proof relies on a (multidimensional) versio
Externí odkaz:
http://arxiv.org/abs/2112.05042
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 number $\omega$ has chromatic number at most $17\omega^4$. This impro
Externí odkaz:
http://arxiv.org/abs/2108.05611
Autor:
Abrahamsen, Mikkel, Walczak, Bartosz
For smooth convex disks $A$, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes $G^{\text{hom}}(A)$ and $G^{\text{sim}}(A)$ of intersection graphs that can be obtained from homothets and similarities of $A$, re
Externí odkaz:
http://arxiv.org/abs/2108.04588
Autor:
Walczak, Bartosz
Publikováno v:
In European Journal of Combinatorics March 2024 117