Coloring and the Lovász Local Lemma
Coloring and the Lovász Local Lemma
复制标题
DOI：
10.1016/j.aml.2009.02.008
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Xing Chen;Zhihua Du;J. Meng
中科院分区：
文献类型：
--
作者：
Xing Chen;Zhihua Du;J. Meng
Lovász局部引理给出了一个超图是2-可着色的充分条件，也就是说，有一个点着色为蓝色或红色，使得没有边是单色的。该方法给出了一个一般性定理，例如，如果H是一个超图，其中每条边至少包含9个点，并且每条边中的每个点至多包含11条边，则H是2-可着色的。本文利用局部引理的“不平衡”形式，给出了超图的t-染色和超图的2-染色的充分条件，使得每边至少含有2个点。
The Lovász Local Lemma yields sufficient conditions for a hypergraph to be 2-colorable, that is, to have a coloring of the points blue or red such that no edge is monochromatic. The method yields a general theorem, which shows for example, if H is a hypergraph in which each edge contains at least 9 points and each point is contained in at most 11 edges, then H is 2-colorable. In this paper, we use the ‘lopsided’ version of the Local Lemma to give some sufficient conditions on t-coloring to hypergraphs and 2-coloring to hypergraphs such that each edge contains at least 2 points of each color.