31 citations · 256 across the 67 of their papers we have counts for
9 papers · 1 filter
Treewidth of grid subsets
Eli Berger, Zdenek Dvorak, Sergey Norin
Let Q_n be the graph of n times n times n cube with all non-decreasing diagonals (including the facial ones) in its constituent unit cubes. Suppose that a subset S of V(Q_n) separa…
Complete graph immersions and minimum degree
Zdeněk Dvořák, Liana Yepremyan
An immersion of a graph H in another graph G is a one-to-one mapping phi:V(H)->V(G) and a collection of edge-disjoint paths in G, one for each edge of H, such that the path P_{uv}…
Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations
Zdenek Dvorak, Daniel Kral, Robin Thomas
We give a linear-time algorithm to decide 3-colorability (and find a 3-coloring, if it exists) of quadrangulations of a fixed surface. The algorithm also allows to prescribe the co…
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
Zdenek Dvorak, Luke Postle
We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring…
Planar graphs have two-coloring number at most 8
Zdeněk Dvořák, Adam Kabela, Tomáš Kaiser
We prove that the two-colouring number of any planar graph is at most 8. This resolves a question of Kierstead et al. [SIAM J. Discrete Math.~23 (2009), 1548--1560]. The result is…
Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles
Zdeněk Dvořák, Bernard Lidický
We study 3-coloring properties of triangle-free planar graphs with two precolored 4-cycles and that are far apart. We prove that either every precoloring of $C_1\cu…