On 2-Colorings of Hypergraphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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
Pages (from-to)112-135
Number of pages24
JournalJournal of Graph Theory
Issue number2
Publication statusPublished - 1 Oct 2015


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

ASJC Scopus subject areas

  • Geometry and Topology


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

Cite this