31 citations · 256 across the 67 of their papers we have counts for
7 papers · 1 filter
Constant-factor approximation of domination number in sparse graphs
Zdenek Dvorak
The k-domination number of a graph is the minimum size of a set X such that every vertex of G is in distance at most k from X. We give a linear time constant-factor approximation a…
Choosability of planar graphs of girth 5
Zdenek Dvorak, Ken-ichi Kawarabayashi
Thomassen proved that any plane graph of girth 5 is list-colorable from any list assignment such that all vertices have lists of size two or three and the vertices with list of siz…
Testing first-order properties for subclasses of sparse graphs
Zdenek Dvorak, Daniel Kral, Robin Thomas
We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nesetril and Ossona de Mend…
Classes of graphs with small rank decompositions are chi-bounded
Zdenek Dvorak, Daniel Kral
A class of graphs G is chi-bounded if the chromatic number of graphs in G is bounded by a function of the clique number. We show that if a class G is chi-bounded,then every class o…
Bipartizing fullerenes
Zdenek Dvorak, Bernard Lidicky, Riste Skrekovski
A fullerene graph is a cubic bridgeless planar graph with twelve 5-faces such that all other faces are 6-faces. We show that any fullerene graph on n vertices can be bipartized by…
Graphs with two crossings are 5-choosable
Zdeněk Dvořák, Bernard Lidický, Riste Škrekovski
A graph G is k-choosable if G can be properly colored whenever every vertex has a list of at least k available colors. Thomassen's theorem states that every planar graph is 5-choos…