The list-coloring function of signed graphs (Q6136674)

Let \(G\) be a graph. Together with a function \(\sigma:E(G)\rightarrow\{-1,1\}\) is \(\Sigma=(G,\sigma)\) a signed graph. A \(k\)-coloring of \(\Sigma\) is a map \(V(G)\rightarrow\{0,\pm 1,\dots,\pm t\}\) such that \(c(u)\neq\sigma(e)c(v)\) for every edge \(e=uv\). The number of all \(k\)-colorings of \(\Sigma\) is denoted by \(P(\Sigma,k)\). Let \(L(v)\) be a list of \(\ell\) colors that is given for any vertex \(v\in V(G)\). An \(L\)-coloring of \(\Sigma\) is a coloring \(c\) such that \(c(v)\in L(v)\) for every \(v\in V(G)\) and \(P(\Sigma,L)\) denotes the number of all \(L\)-colorings of \(\Sigma\). Finally, the minimum number of \(L\)-colorings of \(\Sigma\) over all possible list assignments \(L\) of length \(\ell\) is denoted by \(P_t(\Sigma,\ell)\). The main result of this contribution is that if \(\ell\) is greater than a specific function of the number of edges, then \(P_t(\Sigma,\ell)=P(\Sigma,\ell)\). The same equality was proven by \textit{A. V. Kostochka} and \textit{A. F. Sidorenko} [Ann. Discrete Math. 51, 375--384 (1992; \url{doi:10.1016/S0167-5060(08)70659-9})] for chordal graphs for any \(\ell\). The step toward arbitrary graphs was done by \textit{Q. Donner} [J. Graph Theory 16, No. 3, 239--245 (1992; Zbl 0754.05038)] who showed that the equality holds for large enough \(\ell\). Later, \textit{C. Thomassen} [J. Comb. Theory, Ser. B 99, No. 2, 474--479 (2009; Zbl 1197.05061)] shown that \(\ell>10^n\), \(n=|V(G)|\), is enough for the mentioned equality to hold. Hence, the present result is the improvement of the previous effort on this topic.