Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs

A hypergraph H on n vertices and m edges is said to be nearly-intersecting if every edge of H intersects all but at most polylogarthmically many (in m and n) other edges. Given lists of colors L(v), for each vertex v∈V, H is said to be L-(list) colorable, if each vertex can be assigned a color from its list such that no edge in H is monochromatic. We show that list-colorability for any nearly intersecting hypergraph, and lists drawn from a set of constant size, can be checked in quasi-polynomial time in m and n.