Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs

Michael A. Henning*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


In this paper, we continue our study of 2-colorings in hypergraphs (see, Henning and Yeo, 2013). A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. It is known (see Thomassen, 1992) that every 4-uniform 4-regular hypergraph is 2-colorable. Our main result in this paper is a strengthening of this result. For this purpose, we define a vertex in a hypergraph H to be a free vertex in H if we can 2-color V(H)∖{v} such that every hyperedge in H contains vertices of both colors (where v has no color). We prove that every 4-uniform 4-regular hypergraph has a free vertex. This proves a conjecture in Henning and Yeo (2015). Our proofs use a new result on not-all-equal 3-SAT which is also proved in this paper and is of interest in its own right.

Original languageEnglish
JournalDiscrete Mathematics
Issue number8
Pages (from-to)2285-2292
Publication statusPublished - 2018



  • 2-colorable
  • Bipartite
  • Free vertex
  • Hypergraphs
  • NAE-3-SAT
  • Transversal

Cite this