On 2-Colorings of Hypergraphs

Michael A. Henning*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


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.

Original languageEnglish
JournalJournal of Graph Theory
Issue number2
Pages (from-to)112-135
Publication statusPublished - 2015
Externally publishedYes


  • 2-colorable
  • bipartite
  • blocking sets
  • even dicycles. AMS subject classification: 05C69
  • hypergraphs


Dive into the research topics of 'On 2-Colorings of Hypergraphs'. Together they form a unique fingerprint.

Cite this