### Abstract

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 language | English |
---|---|

Journal | Discrete Mathematics |

Volume | 341 |

Issue number | 8 |

Pages (from-to) | 2285-2292 |

ISSN | 0012-365X |

DOIs | |

Publication status | Published - 2018 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Mathematics*,

*341*(8), 2285-2292. https://doi.org/10.1016/j.disc.2018.05.002