Some Concepts in List Coloring

Abstract

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 }^{\prime }$-critical graph is ${\chi }^{\prime }$-critical, and the equivalence of this conjecture to the well-known list coloring conjecture is shown.