zbMATH — the first resource for mathematics

Some concepts in list coloring. (English) Zbl 1043.05046
In this paper the uniquely list colorable graphs and the list critical graphs are discussed. It is proved that every triangle-free uniquely $$(k+1)$$-colorable graph is uniquely $$k$$-list colorable (Theorem 1), and every planar graph has $$m$$-number at most 4 (Theorem 5). Furthermore, all 3-list critical graphs are characterized (Theorem 7). It is conjectured that every $$\chi'_l$$-critical graph is $$\chi'$$-critical and the equivalence of this conjecture to the well-known list coloring conjecture is proved, which is very interesting and valuable.
By the way, the authors say that it seems that if $$f(v) = k$$ for each vertex $$v$$ of graph $$G$$, the equality in Theorem 2 does not hold. But they do not provide the proof strictly.

MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text: