On the colorability of bi-hypergraphs

Abstract

A {\it mixed hypergraph} $\mathcal{H}=(\mathcal{V},\mathcal{C},\mathcal{D})$ consists of the vertex set $\mathcal{V}$ and two families of subsets of $2^{\mathcal{V}}$: the family $\mathcal{C}$ of co-edges and the family $\mathcal{D}$ of edges. $\mathcal{H}$ is said to be colorable if there is a mapping $f$ from $\mathcal{V}$ to the set of positive integers such that $|\{f(v):v\in e\}|<|e|$ for each $e\in \mathcal{C}$ and $|\{f(v):v\in e\}|>1$ for each $e\in \mathcal{D}$. There exist mixed hypergraphs which are uncolorable, and quite little about these mixed hypergraphs is known. A mixed hypergraph is called a bi-hypergraph if its co-edge set and edge set are the same. In this article, we first apply Lovász local lemma to show that any $r$-uniform bi-hypergraph with $r\ge 4$ is colorable if every edge is incident to less than $(r-1{)}^{r-1}{e}^{-1}-1$ other edges, where $e$ is the base of natural logarithms. Then, we show that among all the uncolorable $3$-uniform bi-hypergraphs, the smallest size of a minimal one is ten, which answers a question raised by Tuza and Voloshin in 2000. As an extension, we provide a minimal uncolorable $3$-uniform bi-hypergraph of order $n$ and size at most $\frac{7n}{3}-4$ for every $n\ge 6$.

19 pages, 4 figures