31 citations · 256 across the 67 of their papers we have counts for
4 papers · 1 filter
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…
Triangle-free planar graphs with at most 3-colorings
Zdeněk Dvořák, Luke Postle
Thomassen conjectured that triangle-free planar graphs have exponentially many 3-colorings. Recently, he disproved his conjecture by providing examples of such graphs with vert…
Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs
Zdeněk Dvořák, Abhiruk Lahiri
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of…
Weak Coloring Numbers of Intersection Graphs
Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt +1
Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for each natural number , we seek a vertex ordering such every vertex can (weakly respec…