Every 4-regular 4-uniform hypergraph has a 2-coloring with a free vertex

arXiv1611.08850MaRDI QIDQ6280184FDOQ6280184

Authors: Michael A. Henning, A. Yeo 

Publication date: 27 November 2016

Abstract: In this paper, 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. It is known (see Thomassen [J. Amer. Math. Soc. 5 (1992), 217--229]) 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)setminusv$ 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 known conjecture. 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.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

This page was built for publication: Every 4-regular 4-uniform hypergraph has a 2-coloring with a free vertex

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280184)