22-colorings in Kk-regular Kk-uniform Hypergraphs
22-colorings in Kk-regular Kk-uniform Hypergraphs
复制标题
DOI：
10.1016/j.ejc.2013.04.005
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Michael A. Henning;Anders Yeo
中科院分区：
文献类型：
--
作者：
Michael A. Henning;Anders Yeo
如果没有单色超边的顶点有2-染色，则超图是2-可染的。设Hk表示所有k-一致k-正则超图的类。Lovász局部引理是由ErdöS和Lovász在1975年为解决超图的2-染色问题而提出的，它意味着每个超图H∈Hk都是2-可染的，只要有k≥9。4(1988)30 3-30 6]证明了一个稍强的结果：每个超图H∈Hk是2-可染的，且有k≥8。文献中隐含地知道，对所有k-≥4，正如Vishwanathan[S.Vishwanathan，关于k-一致超图2-染色，J.Combin，J.Combin]所评论的那样，对所有k-一致超图，Alon-Bregman结果是成立的。理论系列。A 101(2003)168-172]，尽管我们还没有看到它被明确证明。为了完备性，我们给出了这一结果的简短证明。正如Alon和Bregman所说，当k=3时，结果是不正确的，考虑Fano平面可以看出这一点。本文的主要结果是对上述结果的加强。为此，我们将超图H中的一个顶点集合X定义为H中的自由集，如果我们可以2-∖V(H)X，使得H中的每条边至少接收到每种颜色的一个顶点。等价地，如果X是H中两个不相交断面的补集，则X是H中的自由集。对于每个k≥13，我们证明了每个n阶超图H∈Hk至少有一个大小为n/5的自由集。对于任意ϵ，其中0<；ϵ<；1且对足够大的k，我们证明了每个n阶超图H∈Hk至少有一个大小为Ckn的自由集，其中Ck=1−6(1+ϵ)ln(K)/k，因此Ck→1为k→∞。作为应用，我们证明了具有足够大的最小度k的n个顶点的图的总约束控制数至多为12(1−ck)n，这显著地改进了已知的12n+1的界。
A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. Let Hkdenote the class of all k-uniform k-regular hypergraphs. The Lovász Local Lemma, devised by Erdös and Lovász in 1975 to tackle the problem of hypergraph 2-colorings, implies that every hypergraph H∈Hkis 2-colorable, provided k≥9. Alon and Bregman [N. Alon, Z. Bregman, Every 8-uniform 8-regular hypergraph is 2-colorable, Graphs Combin. 4 (1988) 303–306] proved the slightly stronger result that every hypergraph H∈Hkis 2-colorable, provided k≥8. It is implicitly known in the literature that the Alon–Bregman result is true for all k≥4, as remarked by Vishwanathan [S. Vishwanathan, On 2-coloring certain k-uniform hypergraphs, J. Combin. Theory Ser. A 101 (2003) 168–172] even though we have not seen it explicitly proved. For completeness, we provide a short proof of this result. As remarked by Alon and Bregman the result is not true when k=3, as may be seen by considering the Fano plane. Our main result in this paper is a strengthening of the above results. For this purpose, we define a set X of vertices in a hypergraph H to be a free set in H if we can 2-color V(H)∖X such that every edge in H receives at least one vertex of each color. Equivalently, X is a free set in H if it is the complement of two disjoint transversals in H. For every k≥13, we prove that every hypergraph H∈Hkof order n has a free set of size at least n/5. For any ϵ where 0<ϵ<1 and for sufficiently large k, we prove that every hypergraph H∈Hkof order n has a free set of size at least ckn, where ck=1−6(1+ϵ)ln(k)/k, and so ck→1 as k→∞. As an application, we show that the total restrained domination number of a graph on n vertices with sufficiently large minimum degree k is at most 12(1−ck)n, which significantly improves the best known bound of 12n+1.