English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we continue the study of $2$-colorings in hypergraphs. Ahypergraph is $2$-colorable if there is a $2$-coloring of the vertices with nomonochromatic 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) \setminus \{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 knownconjecture. Our proofs use a new result on not-all-equal $3$-SAT which is alsoproved in this paper and is of interest in its own right.

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