Prove
Lemma 14. Let t≥2 be an integer, let h(P)<t , and let X⊆V(P) . Then | v∈V(P)…Proposition 5. There are an absolute positive integer L and an absolute integer…Lemma 11. The following hold for every finite graph P . If H is a subgraph of P…Proposition
Write R=P-X-Y and s=ℓ(R) , and set u=s+(4L+d+5)t. We show that P is u -choosable. Given any lists of size at least u , first restrict each list to exactly u entries. Denote the resulting assignment by L . Its total palette C=⋃_ v∈V(P) L(v) is finite, but its size is otherwise unrestricted. Independently for each color in C , reserve that color with probability p=(2Lt)/(u). Since u≥(4L+d+5)t>2Lt , this is a probability strictly between zero and one. Reservation is global: all occurrences of a color are reserved together. For each vertex v , the number Z_v of reserved entries in L(v) has distribution Bin(u,p) and mean μ=2Lt . This mean is independent of s , and overlaps between different lists do not affect this marginal distribution. For completeness, for every real λ its exponential moment obeys 𝔼 e^ λZ_v =(1-p+pe^λ)^u ≤(μ(e^λ-1)). Markov's inequality with λ=-2 and λ=2 , respectively, gives (Z_v<μ/2) , ≤(-(1-2)/(2)μ), ; (Z_v>2μ) , ≤(-(22-1)μ). Let T= v∈V(P) X:|N_P(v)∩X|≥t . By Lemma 14, |T|≤|X| 2 . Put η=(1-2)/2,\,22-1>0 . A union bound using and shows that the probability of either of the failures Z_x<Lt some x∈X, Z_v>4Lt some v∈T is at most (|X|+|T|)e^ -2ηLt ≤2t^ 11/5 e^ -2ηLt <1 for sufficiently large t . There are only polynomially many tested vertices even if P has arbitrarily many vertices. No independence between different vertices' failure events is required. Fix a reservation for which neither failure occurs. Use the reserved entries to color P[X] . They provide at least Lt colors at each of its vertices, and Proposition 5 applies because |X|≤t^ 11/10 and h(P[X])<t . If X is empty this step is vacuous. Write the coloring as φ_X . For each vertex v∉X , delete from its list the colors on its neighbors in X : L_1(v)= L(v)φ_X(x):x∈N_P(v)∩X. If v∈T , every deleted entry is reserved, so at most 4Lt entries are deleted. If v∉T , fewer than t entries are deleted because v has fewer than t neighbors in X . In particular, the uniform bound | L_1(v)|≥u-(4L+1)t=s+(d+4)t holds. We have removed only colors actually used on neighbors in X ; there is no need to discard all reserved entries at the other vertices. The bound in is at least dt+1 . By Lemma 11, the dt -degenerate graph P[Y] therefore has a coloring φ_Y from these lists. This coloring has no conflict with φ_X . Finally, at each vertex of R delete from L_1(v) the colors used by its neighbors in Y . There are at most dt such neighbors, so its resulting list has size at least u-(4L+1)t-dt=s+4t≥s. The definition of s=ℓ(R) supplies a coloring of R from these lists, with nothing to do if R is empty. The three colorings combine properly, since both pruning steps excluded colors used on neighbors in the previously colored parts. We have colored every u -list assignment on P , proving ℓ(P)≤u=ℓ(P-X-Y)+c_dt. Only the fixed cutoff in Proposition 5 and the last exponential-versus-polynomial estimate impose a sufficiently-large- t requirement. Neither depends on the graph order or palette size.