×

2-colorings in \(k\)-regular \(k\)-uniform hypergraphs. (English) Zbl 1292.05112

Summary: A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. Let \(\mathcal H_k\) denote 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\in\mathcal H_k\) is 2-colorable, provided \(k\geq9\). N. Alon and Z. Bregman [Graphs Comb. 4, No. 4, 303–306 (1988; Zbl 0725.05061)] proved the slightly stronger result that every hypergraph \(H \in\mathcal H_k\) is 2-colorable, provided \(k\geq8\). It is implicitly known in the literature that the Alon-Bregman result is true for all \(k\geq4\), as remarked by S. Vishwanathan [J. Comb. Theory, Ser. A 101, No. 1, 168–172 (2003; Zbl 1010.05027)] 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)\setminus 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\geq13\), we prove that every hypergraph \(H\in\mathcal H_k\) of order \(n\) has a free set of size at least \(n/5\). For any \(\epsilon\) where \(0<\epsilon<1\) and for sufficiently large \(k\), we prove that every hypergraph \(H\in\mathcal H_k\) of order \(n\) has a free set of size at least \(c_kn\), where \(c_k=1-6(1+\epsilon)\ln(k)/k\), and so \(c_k\to1\) as \(k \to\infty\). 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 \(\frac{1}{2}(1-c_k)n\), which significantly improves the best known bound of \(\frac{1}{2}n+1\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Bregman, Z., Every 8-uniform 8-regular hypergraph is 2-colorable, Graphs Combin., 4, 303-306 (1988) · Zbl 0725.05061
[2] Baŕat, J.; Marcugini, S.; Pambianco, F.; Szőnyi, T., Note on disjoint blocking sets in Galois planes, J. Combin. Des., 14, 149-158 (2005) · Zbl 1092.51002
[3] Bruen, A. A., Blocking sets in finite projective planes, SIAM. J. Appl. Math., 21, 380-392 (1971) · Zbl 0252.05014
[4] Cameron, P.; Mazzocca, F., Bijections which preserve blocking sets, Geom. Dedicata, 21, 219-229 (1986) · Zbl 0619.05001
[5] Cameron, P.; Mazzocca, F.; Meshulam, F., Dual blocking sets in projective and affine planes, Geom. Dedicata, 27, 203-207 (1988) · Zbl 0659.51013
[6] Chen, X.; Du, Z.; Meng, J., Coloring and the Lovász Local Lemma, Appl. Math. Lett., 23, 3, 219-221 (2010) · Zbl 1213.05186
[7] Erdös, P.; Lovász, L., Problems and results on 3-chromatic hypergraphs and some related questions, (Hajnal, A.; Rado, R.; Sos, V. T., Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday), Vol. II (1975), North-Holland), 609-627
[8] Funk, M.; Jackson, B.; Labbate, D.; Sheehan, J., Det-extremal cubic bipartite graphs, J. Graph Theory, 44, 50-64 (2003) · Zbl 1029.05096
[9] Henning, M. A., Recent results on total domination in graphs: a survey, Discrete Math., 309, 32-63 (2009) · Zbl 1219.05121
[10] Henning, M. A.; Yeo, A., Hypergraphs with large transversal number and with edge sizes at least three, J. Graph Theory, 59, 326-348 (2008) · Zbl 1211.05091
[11] Henning, M. A.; Yeo, A., Total domination in 2-connected graphs and in graphs with no induced 6-cycles, J. Graph Theory, 60, 55-79 (2009) · Zbl 1189.05131
[12] Hirschfeld, J. W.P., Projective Geometries Over Finite Fields (1998), Oxford University Press · Zbl 0899.51002
[13] Hirschfeld, J. W.P.; Szőnyi, T., Constructions of large arcs and blocking sets in finite planes, European J. Combin., 12, 499-511 (1991) · Zbl 0752.05015
[14] Jiang, H.; Kang, L.; Shan, E., Total restrained domination in cubic graphs, Graphs Combin., 25, 341-350 (2009) · Zbl 1211.05116
[15] König, D., Über Graphen und ihre Anwendung auf Determinantheorie und Mengenlehre, Math. Ann., 77, 453-465 (1916) · JFM 46.0146.03
[16] Lovász, L., Coverings and colorings of hypergraphs, Proc. 4th Southeastern Conf. on Comb., Utilitas Math., 3-12 (1973) · Zbl 0322.05114
[18] Seymour, P. D., On the two coloring of hypergraphs, Q. J. Math., 25, 303-312 (1974) · Zbl 0299.05122
[19] Southey, J.; Henning, M. A., An improved upper bound on the total restrained domination number in cubic graphs, Graphs Combin., 28, 547-554 (2012) · Zbl 1256.05177
[20] Thomassé, S.; Yeo, A., Total domination of graphs and small transversals of hypergraphs, Combinatorica, 27, 473-487 (2007) · Zbl 1164.05052
[21] Thomassen, C., The even cycle problem for directed graphs, J. Amer. Math. Soc., 5, 217-229 (1992) · Zbl 0760.05051
[22] Turan, P., An extremal problem in graph theory (hungarian), Mat. Fiz. Lapok, 48, 436-452 (1941)
[23] Vishwanathan, S., On 2-coloring certain \(k\)-uniform hypergraphs, J. Combin. Theory Ser. A, 101, 168-172 (2003) · Zbl 1010.05027
[24] Yeo, A., Relationships between total domination, order, size and maximum degree of graphs, J. Graph Theory, 55, 4, 325-337 (2007) · Zbl 1123.05070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.