Complexity of unique list colorability

AbstractGiven a list L(v) for each vertex v, we say that the graph G is L-colorable if there is a proper vertex coloring of G where each vertex v takes its color from L(v). The graph is uniquely k-list colorable if there is a list assignment L such that ∣L(v)∣=k for every vertex v and the graph has exactly one L-coloring with these lists. Mahdian and Mahmoodian [M. Mahdian, E.S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. 51 (1999) 295–305] gave a polynomial-time characterization of uniquely 2-list colorable graphs. Answering an open question from [M. Ghebleh, E.S. Mahmoodian, On uniquely list colorable graphs, Ars Combin. 59 (2001) 307–318; M. Mahdian, E.S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. 51 (1999) 295–305], we show that uniquely 3-list colorable graphs are unlikely to have such a nice characterization, since recognizing these graphs is Σ2p-complete