Vertex colouring edge weightings: A logarithmic upper bound on weight-choosability

A graph G is said to be (k, m)-choosable if for any assignment of k-element lists (formula presented) to the vertices (formula presented) and any assignment of m-element lists (formula presented) to the edges (formula presented) there exists a total weighting w: V (G) ∪ E(G) → R of G such that w(v) ∈ Lv for any vertex (formula presented) and (formula presented)) and furthermore, such that for any pair of adjacent vertices u, v, we have (formula presented) w(e), where E(u) and E(v) denote the edges incident to u and v respectively.

In this paper we give an algorithmic proof showing that any graph G without isolated edges is (formula presented)-choosable, where ∆(G) denotes the maximum degree in G.