Near-optimal list colorings

We show that a simple variant of a naive coloring procedure can be used to list color the edges of a k-uniform linear hypergraph of maximum degree a p rovided every vertex has a list of at least Delta + c(log Delta)(4)Delta (1 -(1/k)) available colors where c is a constant which depends on k). We can extend this to color hypergraphs of maximum codegree o(Delta) with Delta o(Delta) colors. This improves earlier results of Kahn and our techniques a re quite similar. We also develop efficient algorithms to obtain such color ings when a is constant. (C) 2000 John Wiley & Sons, Inc.