Brooks‐type theorems for choosability with separation

We consider the following type of problems. Given a graph G = ( V , E ) and lists L ( v ) of allowed colors for its vertices v ∈ V such that | L ( v )| = p for all v ∈ V and | L ( u ) ∩ L ( v )| ≤ c for all uv ∈ E , is it possible to find a “list coloring,” i.e., a color f ( v ) ∈ L ( v ) for each v ∈ V , so that f ( u ) ≠ f ( v ) for all uv ∈ E ? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ $\sqrt{5.437c\Delta }$ . Apart from a multiplicative constant, the result is tight, as lists of length $\sqrt{0.5c\Delta }$ may be necessary. Moreover, for G = K n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o (1)) $\sqrt{n}$ . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998