31 citations · 256 across the 67 of their papers we have counts for
8 papers · 1 filter
On distance r-dominating and 2r-independent sets in sparse graphs
Zdeněk Dvořák
Dvorak (2013) gave a bound on the minimum size of a distance r dominating set in the terms of the maximum size of a distance 2r independent set and generalized coloring numbers, th…
On classes of graphs with strongly sublinear separators
Zdeněk Dvořák
For real numbers c,epsilon>0, let G_{c,epsilon} denote the class of graphs G such that each subgraph H of G has a balanced separator of order at most c|V(H)|^{1-epsilon}. A class o…
Induced 2-degenerate Subgraphs of Triangle-free Planar Graphs
Zdeněk Dvořák, Tom Kelly
A graph is -degenerate if every subgraph has minimum degree at most . We provide lower bounds on the size of a maximum induced 2-degenerate subgraph in a triangle-free planar…
Additive non-approximability of chromatic number in proper minor-closed classes
Zdeněk Dvořák, Ken-ichi Kawarabayashi
Robin Thomas asked whether for every proper minor-closed class C, there exists a polynomial-time algorithm approximating the chromatic number of graphs from C up to a constant addi…
Induced subdivisions and bounded expansion
Zdeněk Dvořák
We prove that for every graph H and for every integer s, the class of graphs that do not contain K_s, K_{s,s}, or any subdivision of H as an induced subgraph has bounded expansion;…
Thin graph classes and polynomial-time approximation schemes
Zdeněk Dvořák
Baker devised a powerful technique to obtain approximation schemes for various problems restricted to planar graphs. Her technique can be directly extended to various other graph c…