On list critical graphs

In this paper we discuss some basic properties of kk-list critical graphs. A graph GG is kk-list critical   if there exists a list assignment LL for GG with |L(v)|=k−1|L(v)|=k−1 for all vertices vv of GG such that every proper subgraph of GG is LL-colorable, but GG itself is not LL-colorable. This generalizes the usual definition of a kk-chromatic critical graph, where L(v)={1,…,k−1}L(v)={1,…,k−1} for all vertices vv of GG. While the investigation of kk-critical graphs is a well established part of coloring theory, not much is known about kk-list critical graphs. Several unexpected phenomena occur, for instance a kk-list critical graph may contain another one as a proper induced subgraph, with the same value of kk. We also show that, for all 2≤p≤k2≤p≤k, there is a minimal kk-list critical graph with chromatic number pp. Furthermore, we discuss the question, for which values of kk and nn is the complete graph KnKnkk-list critical. While this is the case for all 5≤k≤n5≤k≤n, KnKn is not 4-list critical if nn is large.