A characterization of uniquely 2-list colorable graphs (Q2761069)

A graph is called uniquely \(k\)-list colorable if there exists an assignment of lists of size \(k\) to its vertices such that this list assignment allows a unique proper coloring which colors each vertex by a color from the list assigned to this vertex. (A coloring is proper if adjacent vertices receive distinct colors.) The main result of the paper is a complete characterization of uniquely 2-list colorable graphs as graphs which contain at least one block which is neither a cycle, nor a complete graph nor a complete bipartite graph. Examples of uniquely \(k\)-list colorable graphs for \(k>2\) are given.