We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On 2-Colorings of Hypergraphs.
- Authors
Henning, Michael A.; Yeo, Anders
- Abstract
In this article, we continue the study of 2‐colorings in hypergraphs. A hypergraph is 2‐colorable if there is a 2‐coloring of the vertices with no monochromatic hyperedge. Let Hk denote the class of all k‐uniform k‐regular hypergraphs. It is known (see Alon and Bregman [Graphs Combin. 4 (1988) 303–306] and Thomassen [J. Amer. Math. Soc. 5 (1992), 217–229] that every hypergraph H ∊ Hk is 2‐colorable, provided K ≥4 . As remarked by Alon and Bregman the result is not true when K = 3, as may be seen by considering the Fano plane. Indeed there are several constructions for building infinite families of hypergraphs in H3 that are not 2‐colorable. 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. We conjecture that for K ≥4, every hypergraph H ∊ Hk has a free set of size K - 3 in H. We show that the bound k - 3 cannot be improved for any K ≥4 and we prove our conjecture when k ∊ {5, 6, 7, 8}. Our proofs use results from areas such as transversal in hypergraphs, cycles in digraphs, and probabilistic arguments.
- Subjects
HYPERGRAPHS; GRAPH theory; FUZZY hypergraphs; GEOMETRIC vertices; ANGLES
- Publication
Journal of Graph Theory, 2015, Vol 80, Issue 2, p112
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.21843