Extension of a list coloring problem (Q2488686)

For a graph \(G\), let \(f(G)\) be the minimum integer \(k\) such that the graph formed from \(G\) by adding \(k\) independent vertices and joining each of them with all vertices of \(G\) is not \(| V(G)| \)-choosable. The quantity \(f(G)\) is related to some properties of Nordhaus-Gaddum type and it was studied previously by \textit{S. Gravier, F. Maffray}, and \textit{B. Mohar} [Discrete Math. 268, 303--308 (2003; Zbl 1018.05028)] who proposed a general conjecture on the value of \(f(G)\). If \(G\) is a triangle-free graph of order \(n\), their conjecture asserts that \(f(G) = {n\choose 2}^{\mu(G)} n^{n-2\mu(G)}\), where \(\mu(G)\) is the size of the maximum matching of \(G\). Gravier et al. proved that their conjecture holds for trees, and the authors of the paper under review extend the result to all forests.