5 papers
Towards Characterization of 5-List-Colorability of Toroidal Graphs
Zdeněk Dvořák, Félix Moreno Peñarrubia
Through computer-assisted enumeration, we list minimal obstructions for 5-choosability of graphs on the torus with the following additional property: There exists a cyclic system o…
A note on local search for hitting sets
Zdeněk Dvořák
Let be a property of pairs , where is a graph and . In the \emph{minimum -hitting set problem}, given an input graph , we want to find a small…
An efficient implementation and a strengthening of Alon-Tarsi list coloring method
Zdeněk Dvořák
As one of the first applications of the polynomial method in combinatorics, Alon and Tarsi gave a way to prove that a graph is choosable (colorable from any lists of prescribed siz…
Representation of short distances in structurally sparse graphs
Zdeněk Dvořák
A partial orientation of a graph is a weak -guidance system if for any two vertices at distance at most in , there exists a shortest path between them s…
Approximation metatheorems for classes with bounded expansion
Zdeněk Dvořák
We give a number of approximation metatheorems for monotone maximization problems expressible in the first-order logic, in substantially more general settings than the previously k…