## Abstract

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

Journal | Journal of Graph Theory |

Volume | 80 |

Issue number | 2 |

Pages (from-to) | 112-135 |

ISSN | 0364-9024 |

DOIs | |

Publication status | Published - 2015 |

Externally published | Yes |

## Keywords

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