8 citations · 8 across the 2 of their papers we have counts for
4 papers · 1 filter
Three-coloring triangle-free planar graphs in linear time
Zdenek Dvorak, Ken-ichi Kawarabayashi, Robin Thomas
Grotzsch's theorem states that every triangle-free planar graph is 3-colorable. Several relatively simple proofs of this fact were provided by Thomassen and other authors. It is ea…
A stronger structure theorem for excluded topological minors
Zdenek Dvorak
Grohe and Marx proved that if G does not contain H as a topological minor, then there exist constants g=O(|V(H)|^4), D and t depending only on H such that G is a clique sum of grap…
Minimum degree condition forcing complete graph immersion
Matt DeVos, Zdeněk Dvořák, Jacob Fox +3
An immersion of a graph into a graph is a one-to-one mapping and a collection of edge-disjoint paths in , one for each edge of , such that the path…
Sub-exponentially many 3-colorings of triangle-free planar graphs
Arash Asadi, Zdenek Dvorak, Luke Postle +1
Thomassen conjectured that every triangle-free planar graph on n vertices has exponentially many 3-colorings, and proved that it has at least 2^[n^(1/12)/20000] distinct 3-coloring…