31 citations · 256 across the 67 of their papers we have counts for
6 papers · 2 filters
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…
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;…
Triangle-free planar graphs with small independence number
Zdeněk Dvořák, Jordan Venters
Since planar triangle-free graphs are 3-colourable, such a graph with n vertices has an independent set of size at least n/3. We prove that unless the graph contains a certain obst…
Do triangle-free planar graphs have exponentially many 3-colorings?
Zdeněk Dvořák, Jean-Sébastien Sereni
Thomassen conjectured that triangle-free planar graphs have an exponential number of -colorings. We show this conjecture to be equivalent to the following statement: there exist…