A relation between choosability and uniquely list colorability (Q2496207)

A list assignment \(L\) of a graph \(G\) is a function that assigns a set of colors to each vertex of \(G\). Graph \(G\) is (uniquely) \(L\)-colorable if there is at least (exactly) one function that assigns to each vertex \(v\) of \(G\) a color from \(L(v)\) such that any two adjacent vertices are assigned distinct colors. The definitions of an edge-list assignment and a uniquely \(L\)-edge-colorable graph are analogous. The main result of this paper says that if \(G\) is a uniquely \(L\)-colorable graph with \(n\) vertices and \(m\) edges such that the sum of \(| L(v)| \) over all vertices \(v\) of \(G\) equals \(n+m\), then \(G\) is also \(L'\)-colorable for any list assignment \(L'\) satisfying \(| L'(v)| =| L(v)| \) for each vertex \(v\) of \(G\). The proof is based on an algebraic technique developed by \textit{N. Alon} and \textit{M. Tarsi} [Combinatorica 12, No.~2, 125--134 (1992; Zbl 0756.05049)]. As a corollary, it is shown that if a connected non-regular multigraph with an edge-list assignment \(L\) satisfies \(L(\{u,v\})=\max\{d(u),d(v)\}\) for each edge \(\{u,v\}\), then it is not uniquely \(L\)-edge-colorable. The authors conjecture that this result holds also for any regular graph \(G\) of degree at least two and verify it in the case that \(G\) is bipartite.