On a list-coloring problem (Q1398274): Difference between revisions

In this paper the function \(f(G)\) is defined for a graph \(G\) as the smallest integer \(k\) such that the join of \(G\) with a stable set of size \(k\) is not \(|V(G)|\)-choosable. This function was introduced recently in order to describe extremal graphs for a list-coloring version of a famous inequality due to Nordhaus and Gaddum (Dantas et al., Research Report 18, Laboratoire Leibniz-IMAG, Grenoble, 2000). Some bounds and some exact values for \(f(G)\) are determined, e.g., if a graph \(G\) of order \(n\) is not complete, then \(f(G)\geq n^{2}\).