31 citations · 256 across the 67 of their papers we have counts for
9 papers · 1 filter
Density of 5/2-critical graphs
Zdenek Dvorak, Luke Postle
A graph G is 5/2-critical if G has no circular 5/2-coloring (or equivalently, homomorphism to C_5), but every proper subgraph of G has one. We prove that every 5/2-critical graph o…
A structure theorem for strong immersions
Zdenek Dvorak, Paul Wollan
A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removal…
Treewidth of graphs with balanced separations
Zdenek Dvorak, Sergey Norin
We prove that if every subgraph of a graph has a balanced separation of order at most then has treewidth at most . This establishes a linear dependence between the…
Crossing numbers of periodic graphs
Zdenek Dvorak, Bojan Mohar
A graph is periodic if it can be obtained by joining identical pieces in a cyclic fashion. It is shown that the limit crossing number of a periodic graph is computable. This answer…
Sublinear separators, fragility and subexponential expansion
Zdenek Dvorak
Let G be a subgraph-closed graph class with bounded maximum degree. We show that if G has balanced separators whose size is smaller than linear by a polynomial factor, then G has s…
Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs
Zdenek Dvorak, Daniel Kral, Robin Thomas
Let G be a 4-critical graph with t triangles, embedded in a surface of genus g. Let c be the number of 4-cycles in G that do not bound a 2-cell face. We prove that the sum of lengt…