A Characterization of Uniquely $2$-List Colorable Graphs

Abstract

Let $G$ be a graph with $v$ vertices. If there exists a list of colors $S_1,S_2,\dots ,S_v$ on its vertices, each of size $k$, such that there exists a unique proper coloring for $G$ from this list of colors, then $G$ is called a uniquely $k$-list colorable graph. We prove that a connected graph is uniquely $2$-list colorable if and only if at least one of its blocks is not a cycle, a complete graph, or a complete bipartite graph. For each $k$, a uniquely $k$-list colorable graph is introduced.