ALGORITHMIC COMPLEXITY OF LIST COLORINGS

Given a graph G = (V, E) and a finite set L(v) at each vertex upsilon is-an-element-of V, the List Coloring problem asks whether there exist s a function f: V --> or(upsilon is-an-element-of V) L(upsilon) such t hat (i) f(upsilon) is-an-element-of L(upsilon) for each upsilon is-an- element-of V and (ii) f(u) not-equal f(upsilon) whenever u, upsilon is -an-element-of V and uupsilon is-an-element-of E. One of our results s tates that this decision problem remains NP-complete even if all of th e following conditions are met: (1) each set L(upsilon) has at most th ree elements, (2) each ''color'' x is-an-element-of or (upsilon is-an- element-of V) L(v) occurs in at most three sets L(upsilon), (3) each v ertex upsilon is-an-element-of V has degree at most three, and (4) G i s a planar graph. On the other hand, strengthening any of the assumpti ons (1)-(3) yields a polynomially solvable problem. The connection bet ween List Coloring and Boolean Satisfiability is discussed, too.