Vertex colouring edge weightings: a logarithmic upper bound on weight-choosability (Q831336)

Summary: A graph \(G\) is said to be \((k,m)\)-choosable if for any assignment of \(k\)-element lists \(L_v \subset \mathbb{R}\) to the vertices \(v \in V(G)\) and any assignment of \(m\)-element lists \(L_e \subset \mathbb{R}\) to the edges \(e \in E(G)\) there exists a total weighting \(w: V(G) \cup E(G) \rightarrow \mathbb{R}\) of \(G\) such that \(w(v) \in L_v\) for any vertex \(v \in V(G)\) and \(w(e) \in L_e\) for any edge \(e \in E(G)\) and furthermore, such that for any pair of adjacent vertices \(u\), \(v\), we have \(w(u)+ \sum_{e \in E(u)}w(e) \neq w(v)+ \sum_{e \in E(v)}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 \((1, 2 \lceil \log_2(\Delta(G)) \rceil+1)\)-choosable, where \(\Delta(G)\) denotes the maximum degree in \(G\).