A CHARACTERIZATION OF UNIQUELY 2-LIST COLORABLE GRAPHS
Mohammad Mahdian, E. S. Mahmoodian · 1999
Let G be a graph with vertices, and let S 1 ; S 2 ; : : : ; S be a list of colors on its vertices, each of size k. If there exists a unique proper coloring for G from this list of colors, then G is called uniquely k--list colorable graph. We prove that a graph is uniquely 2--list colorable if and only if 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.