58 citations · 549 across the 45 of their papers we have counts for
6 papers · 1 filter
On choosability with separation of planar graphs with lists of different sizes
Hal Kierstead, Bernard Lidický
A (k,d)-list assignment L of a graph G is a mapping that assigns to each vertex v a list L(v) of at least k colors and for any adjacent pair xy, the lists L(x) and L(y) share at mo…
Planar 4-critical graphs with four triangles
Oleg V. Borodin, Zdeněk Dvořák, Alexandr V. Kostochka +2
By the Grunbaum-Aksenov Theorem (extending Grotzsch's Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical…
3-coloring triangle-free planar graphs with a precolored 8-cycle
Zdeněk Dvořák, Bernard Lidický
Let G be a planar triangle-free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3-coloring of C does not extend to a proper 3-coloring o…
4-critical graphs on surfaces without contractible (<=4)-cycles
Zdeněk Dvořák, Bernard Lidický
We show that if G is a 4-critical graph embedded in a fixed surface so that every contractible cycle has length at least 5, then G can be expressed as $G=G'\cup G_1\cup G_2\cup…
On Choosability with Separation of Planar Graphs with Forbidden Cycles
Ilkyoo Choi, Bernard Lidický, Derrick Stolee
We study choosability with separation which is a constrained version of list coloring of graphs. A (k,d)-list assignment L on a graph G is a function that assigns to each vertex v…
Peeling the Grid
Sariel Har-Peled, Bernard Lidický
Consider the set of points formed by the integer grid, and the process that in each iteration removes from the point set the vertices of its convex-hull. Here, we prov…