Total weight choosability of graphs: towards the 1-2-3-conjecture (Q2033917)

The 1-2-3 conjecture states that for every simple graph with no isolated edges (a ``nice'' graph), one can assign weights of 1, 2, or 3 to each edge in such a way that all adjacent pairs of vertices have different total weights of incident edges. Although the conjecture was posed by \textit{M. Karoński} et al. [J. Comb. Theory, Ser. B 91, No. 1, 151--157 (2004; Zbl 1042.05045)], the best known result along these lines is that one can always succeed if weights of 4 or 5 are also permitted, due to \textit{M. Kalkowski} et al. [J. Comb. Theory, Ser. B 100, No. 3, 347--349 (2010; Zbl 1209.05087)]. This paper makes progress on a stronger conjecture about ``total weight \((a,b)\)-choosability''. A simple graph \((V, E)\) is said to be total weight \((a,b)\)-choosable if, given an \(a\)-element set of real numbers \(S_v\) for each vertex \(v\in V\) and a \(b\)-element set of real numbers \(S_e\) for each edge \(e\), it is possible to choose a weight \(w(x)\in S_x\) for each \(x\in V\cup E\) such that no two adjacent vertices share the same total weight (their own weight plus the weights of their incident edges). The total-weight-\((1,3)\) conjecture due to \textit{T.-L. Wong} and \textit{X. Zhu} [J. Graph Theory 66, No. 3, 198--212 (2011; Zbl 1228.05161)] states that every nice graph is total weight \((1,3)\)-chooseable. The total-weight-\((1,3)\) conjecture implies the 1-2-3 conjecture as a special case, by setting \(S_v = \{0\}\) for each vertex \(v\) and \(S_e = \{1,2,3\}\) for each edge \(e\). This paper is the first to prove a theorem of the form ``Every nice graph is total weight \((1,b)\)-choosable'' for a constant \(b\), namely, \(b=17\). It does so by proving an even stronger property, that every nice graph is algebraic total weight \((1,17)\)-choosable, using the combinatorial Nullstellensatz due to \textit{N. Alon} [Comb. Probab. Comput. 8, No. 1--2, 7--29 (1999; Zbl 0920.05026)]. The paper also concludes with several results about classes of graphs that are total weight \((1,2)\)-, \((1,3)\)-, or \((1,4)\)-choosable.