Some Concepts in List Coloring

In this paper, uniquely list colorable graphs are studied. A graph \(G\) is said to be uniquely \(k\)-list colorable if it admits a \(k\)-list assignment from which \(G\) has a unique list coloring. The minimum \(k\) for which \(G\) is not uniquely \(k\)-list colorable is called the \(m\)-number of \(G\). We show that every triangle-free uniquely colorable graph with chromatic number \(k+1\) is uniquely \(k\)-list colorable. A bound for the \(m\)-number of graphs is given, and using this bound it is shown that every planar graph has \(m\)-number at most \(4\). Also, we introduce list criticality in graphs and characterize all \(3\)-list critical graphs. It is conjectured that every \(\chi_\ell’\)-critical graph is \(\chi’\)-critical, and the equivalence of this conjecture to the well-known list coloring conjecture is shown.