23 citations · 134 across the 40 of their papers we have counts for
4 papers · 1 filter
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…
List-coloring apex-minor-free graphs
Zdenek Dvorak, Robin Thomas
A graph H is t-apex if H-X is planar for some subset X of V(H) of size t. For any integer t>=0 and a fixed t-apex graph H, we give a polynomial-time algorithm to decide whether a (…
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…
Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle
Zdenek Dvorak, Dan Kral, Robin Thomas
Let G be a plane graph with exactly one triangle T and all other cycles of length at least 5, and let C be a facial cycle of G of length at most six. We prove that a 3-coloring of…