List Coloring and \(n\)-Monophilic Graphs

Abstract

In 1990, Kostochka and Sidorenko proposed studying the smallest number of list-colorings of a graph \(G\) among all assignments of lists of a given size \(n\) to its vertices. We say a graph \(G\) is \(n\)-monophilic if this number is minimized when identical \(n\)-color lists are assigned to all vertices of \(G\). Kostochka and Sidorenko observed that all chordal graphs are \(n\)-monophilic for all \(n\). Donner (1992) showed that every graph is \(n\)-monophilic for all sufficiently large \(n\). We prove that all cycles are \(n\)-monophilic for all \(n\); we give a complete characterization of \(2\)-monophilic graphs (which turns out to be similar to the characterization of \(2\)-choosable graphs given by Erdős, Rubin, and Taylor in 1980); and for every \(n\) we construct a graph that is \(n\)-choosable but not \(n\)-monophilic.