31 citations · 256 across the 67 of their papers we have counts for
6 papers · 2 filters
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…
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…
3-choosability of planar graphs with (<=4)-cycles far apart
Z. Dvorak
A graph is k-choosable if it can be colored whenever every vertex has a list of at least k available colors. We prove that if cycles of length at most four in a planar graph G are…