31 citations · 256 across the 67 of their papers we have counts for
79 papers · 1 filter
Extremal function for rooted minors
Zdeněk Dvořák
We show that if an n-vertex 5-connected graph has at least 4n-10 edges, then for any choice of five of its vertices, we can contract disjoint connected subgraphs containing these v…
Correspondence coloring of random graphs
Zdenek Dvorak, Liana Yepremyan
We show that Erdős-Rényi random graphs with constant density have correspondence chromatic number ; this matches a prediction from linear Hadwige…
Embedded graph 3-coloring and flows
Caroline Bang, Zdeněk Dvořák, Emily Heath +1
A graph drawn in a surface is a near-quadrangulation if the sum of the lengths of the faces different from 4-faces is bounded by a fixed constant. We leverage duality between color…
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…
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…
Weak diameter coloring of graphs on surfaces
Zdeněk Dvořák, Sergey Norin
Consider a graph drawn on a fixed surface, and assign to each vertex a list of colors of size at least two if is triangle-free and at least three otherwise. We prove that w…