31 citations · 256 across the 67 of their papers we have counts for
4 papers · 1 filter
Product structure of graph classes with strongly sublinear separators
Zdeněk Dvořák, David R. Wood
We investigate the product structure of hereditary graph classes admitting strongly sublinear separators. We characterise such classes as subgraphs of the strong product of a star…
Square roots of nearly planar graphs
Zdeněk Dvořák, Benjamin Moore, Abhiruk Lahiri
We prove that it is NP-hard to decide whether a graph is the square of a 6-apex graph. This shows that the square root problem is not tractable for squares of sparse graphs (or eve…
11/4-colorability of subcubic triangle-free graphs
Zdeněk Dvořák, Bernard Lidický, Luke Postle
We prove that up to two exceptions, every connected subcubic triangle-free graph has fractional chromatic number at most 11/4. This is tight unless further exceptional graphs are e…
On Comparable Box Dimension
Zdenek Dvorák, Daniel Goncalves, Abhiruk Lahiri +2
Two boxes in are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph is the minimum integer such…