research
∙
08/23/2023
Cliquewidth and dimension
We prove that every poset with bounded cliquewidth and with sufficiently...
share
research
∙
02/06/2023
Tight bound on treedepth in terms of pathwidth and longest path
We show that every graph with pathwidth strictly less than a that contai...
research
∙
01/21/2022
Separating polynomial χ-boundedness from χ-boundedness
Extending the idea from the recent paper by Carbonero, Hompe, Moore, and...
research
∙
12/09/2021
A solution to Ringel's circle problem
We construct families of circles in the plane such that their tangency g...
research
∙
08/12/2021
Grounded L-graphs are polynomially χ-bounded
A grounded L-graph is the intersection graph of a collection of "L" shap...
research
∙
08/10/2021
Distinguishing classes of intersection graphs of homothets or similarities of two convex disks
For smooth convex disks A, i.e., convex compact subsets of the plane wit...
research
∙
03/13/2021
Colouring polygon visibility graphs and their generalizations
Curve pseudo-visibility graphs generalize polygon and pseudo-polygon vis...
research
∙
08/03/2020
Approximating pathwidth for graphs of small treewidth
We describe a polynomial-time algorithm which, given a graph G with tree...
research
∙
07/15/2020
Coloring and Maximum Weight Independent Set of Rectangles
In 1960, Asplund and Grünbaum proved that every intersection graph of ax...
research
∙
02/25/2020
Coloring triangle-free L-graphs with O(loglog n) colors
It is proved that triangle-free intersection graphs of n L-shapes in the...
research
∙
10/02/2019
Subexponential-time algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
research
∙
04/10/2019
Planar graphs have bounded nonrepetitive chromatic number
A colouring of a graph is "nonrepetitive" if for every path of even orde...
research
∙
02/27/2018
Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane
It is shown that shift graphs can be realized as disjointness graphs of ...
research
∙
11/05/2017