Graphs are (1,Δ+1)-choosable

Abstract A graph G is ( k , k ′ ) -choosable if the following holds: For any list assignment L which assigns to each vertex v a set L ( v ) of k real numbers, and assigns to each edge e a set L ( e ) of k ′ real numbers, there is a total weighting ϕ : V ( G ) ∪ E ( G ) → R such that ϕ ( z ) ∈ L ( z ) for z ∈ V ∪ E , and ∑ e ∈ E ( u ) ϕ ( e ) + ϕ ( u ) ≠ ∑ e ∈ E ( v ) ϕ ( e ) + ϕ ( v ) for every edge u v . This paper proves that if G is a connected graph of maximum degree Δ ≥ 2 , then G is ( 1 , Δ + 1 ) -choosable.