Exact Algorithms for List-Coloring of Intersecting Hypergraphs

摘要

We show that list-coloring for any intersecting hypergraph of m edges on n vertices, and lists drawn from a set of size at most k, can be checked in quasi-polynomial time (mn)^{o(k^2*log(mn))}.