31 citations · 256 across the 67 of their papers we have counts for
Showing 2016 · cs.DMShow all
3 papers · 2 filters
cs.DM2016★ 2 cited
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…
cs.DM2016★ 4 cited
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…
cs.DM2016
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…