31 citations · 256 across the 67 of their papers we have counts for
9 papers · 2 filters
Immersion in four-edge-connected graphs
Maria Chudnovsky, Zdeněk Dvořák, Tereza Klimošová +1
Fix g>1. Every graph of large enough tree-width contains a g x g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g x g…
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…
Strong immersions and maximum degree
Zdenek Dvorak, Tereza Klimosova
A graph H is strongly immersed in G if G is obtained from H by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removal…
Distance-two coloring of sparse graphs
Zdenek Dvorak, Louis Esperet
Consider a graph and, for each vertex , a subset of neighbors of . A -coloring is a coloring of the elements of so that vertices appearing to…