31 citations · 256 across the 67 of their papers we have counts for
6 papers · 1 filter
List coloring with requests
Zdeněk Dvořák, Sergey Norin, Luke Postle
Let G be a graph with a list assignment L. Suppose a preferred color is given for some of the vertices; how many of these preferences can be respected when L-coloring G? We explore…
Independent sets near the lower bound in bounded degree graphs
Zdenek Dvorak, Bernard Lidicky
By Brook's Theorem, every n-vertex graph of maximum degree at most Delta >= 3 and clique number at most Delta is Delta-colorable, and thus it has an independent set of size at leas…
Graphic TSP in cubic graphs
Zdenek Dvorak, Daniel Kral, Bojan Mohar
We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic…
Triangle-free planar graphs with the smallest independence number
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1
Steinberg and Tovey proved that every n-vertex planar triangle-free graph has an independent set of size at least (n+1)/3, and described an infinite class of tight examples. We sho…
Cyclic Coloring of Plane Graphs with Maximum Face Size 16 and 17
Zdenek Dvorak, Michael Hebdige, Filip Hlasek +2
Plummer and Toft conjectured in 1987 that the vertices of every 3-connected plane graph with maximum face size D can be colored using at most D+2 colors in such a way that no face…
Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm
Zdenek Dvorak, Daniel Kral, Robin Thomas
We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmat…