zbMATH — the first resource for mathematics

On uniquely list colorable graphs. (English) Zbl 1066.05063
Summary: Let \(G\) be a graph with \(n\) vertices and suppose that for each vertex \(v\) in \(G\), there exists a list of \(k\) colors, \(L(v)\), such that there is a unique proper coloring for \(G\) from this collection of lists. Then \(G\) is called a uniquely \(k\)-list colorable graph. Recently M. Mahdian and E. S. Mahmoodian characterized uniquely 2-list colorable graphs. Here we state some results which pave the way in characterization of uniquely \(k\)-list colorable graphs. There is a relationship between this concept and defining sets in graph colorings and critical sets in Latin squares.

05C15 Coloring of graphs and hypergraphs
Full Text: arXiv