Extremal jumps of the Hall number

Given a graph G=(V,E) and sets L(v) of allowed colors for each v∈V, a list coloring of G is an assignment of colors φ(v) to the vertices, such that φ(v)∈L(v) for all v∈V and φ(u)≠φ(v) for all uv∈E. The Hall number of G is the smallest positive integer k such that G admits a list coloring provided that |L(v)|⩾k for every vertex v and, for every X⊆V, the sum—over all colors c—of the maximum number of independent vertices in X whose lists contain c, is at least |X|. We prove that every graph of order n⩾3 has Hall number at most n−2. Combining this upper bound with a construction, we deduce that vertex deletion or edge insertion in a graph of order n>3 may make the Hall number decrease by as much as n−3, and that this estimate is tight for all n. This solves two problems raised by Hilton, Johnson and Wantland [Discrete Applied Math. 94 (1999), 227–245].