Restricted list coloring and Hallʹs condition Original Research Article

If L is a list assignment of colors to the vertices of a graph G of chromatic number χ(G), a certain condition on L and G, known as Hallʹs condition, which is obviously necessary for G to have an L-coloring, is known to be sufficient if and only if each block of G is a clique. We show that if the set of colors from which the lists are drawn has size χ(G) then there exist graphs G for which Hallʹs condition is sufficient for an L-coloring even though not every block of G is a clique. But if the set of colors has size greater than χ(G), then Hallʹs condition is again sufficient if and only if each block of G is a clique.