On list critical graphs
On list critical graphs
复制标题
列出关键图表
DOI：
10.1016/j.disc.2008.05.021
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Voigt
中科院分区：
文献类型：
--
作者：
M. Stiebitz;Z. Tuza;M. Voigt
本文讨论了k-列表临界图的一些基本性质。一个图G是k-列表临界的，如果存在G的列表赋值L，|L（v）|=k−1，使得G的每个真子图都是L-可着色的，但G本身不是L-可着色的。这推广了k-色临界图的通常定义，其中对G的所有顶点v，L（v）={1，.，k −1}。虽然k-临界图的研究是着色理论的一个很好的部分，但对k-列表临界图知之甚少。出现了一些意想不到的现象，例如一个k-列表临界图可能包含另一个具有相同k值的真导出子图。证明了对任意2≤p≤k，存在色数为p的极小k-列临界图，并讨论了k和n的值是完全图的Knk-列临界图的问题.虽然这是所有5≤k≤n的情况，但如果n很大，Knis不是4-列表临界的。
In this paper we discuss some basic properties of k-list critical graphs. A graph G is k-list critical if there exists a list assignment L for G with |L(v)|=k−1 for all vertices v of G such that every proper subgraph of G is L-colorable, but G itself is not L-colorable. This generalizes the usual definition of a k-chromatic critical graph, where L(v)={1,…,k−1} for all vertices v of G. While the investigation of k-critical graphs is a well established part of coloring theory, not much is known about k-list critical graphs. Several unexpected phenomena occur, for instance a k-list critical graph may contain another one as a proper induced subgraph, with the same value of k. We also show that, for all 2≤p≤k, there is a minimal k-list critical graph with chromatic number p. Furthermore, we discuss the question, for which values of k and n is the complete graph Knk-list critical. While this is the case for all 5≤k≤n, Knis not 4-list critical if n is large.