Hall number for list colorings of graphs: Extremal results

Given a graph G=(V,E)G=(V,E) and sets L(v)L(v) of allowed colors for each v∈Vv∈V, a list coloring   of GG is an assignment of colors φ(v)φ(v) to the vertices, such that φ(v)∈L(v)φ(v)∈L(v) for all v∈Vv∈V and φ(u)≠φ(v)φ(u)≠φ(v) for all uv∈Euv∈E. The choice number   of GG is the smallest natural number kk admitting a list coloring for GG whenever |L(v)|≥k|L(v)|≥k holds for every vertex vv. This concept has an interesting variant, called Hall number  , where an obvious necessary condition for colorability is put as a restriction on the lists L(v)L(v). (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order n>3n>3 may make the Hall number decrease by as much as n−3n−3. This estimate is tight for all nn. Tightness is deduced from the upper bound that every graph of order nn has Hall number at most n−2n−2. We also characterize the cases of equality; for n≥6n≥6 these are precisely the graphs whose complements are K2∪(n−2)K1K2∪(n−2)K1, P4∪(n−4)K1P4∪(n−4)K1, and C5∪(n−5)K1C5∪(n−5)K1. Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161–182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227–245] as a function of maximum degree.