If $H=(V,E)$ is a hypergraph and $\kappa \neq \emptyset$ is a cardinal, then a map $c:V\to\kappa$ is called a coloring if the restriction $c\restriction_e$ is non-constant for all $e\in E$ with $|e|\geq 2$. The smallest cardinal $\kappa$ for which a coloring $c:V\to \kappa$ exists, is said to be the chromatic number $\chi(H)$ of $H$.

We say $J\subseteq V$ is independent if $|J\cap e| \leq 1$ for all $e\in E$. We say that a collection ${\cal J}$ of independent sets is an independent covering of $H$ if $\bigcup {\cal J} = V$. The smallest cardinality of any independent covering of $H$ is said to be the independent covering number $j(H)$ of $H$.

It is not difficult to see that if $H$ is a graph, then $j(H) = \chi(H)$.

We say $H$ is $k$-regular for an integer $k\geq 2$ if $|e|=k$ for all $e\in E$.

Question. Given an integer $k\geq 3$ is there a positive integer $C_k$ such that $$j(H) \leq C_k\cdot \chi(H)$$ for all finite $k$-regular hypergraphs $H$?


No, this is false already for $k=3$. Let $A$ and $B$ be disjoint sets of size $n$, and let $H$ be the hypergraph with vertex set $A \cup B$, whose hyperedges are all $3$-subsets $e$ of $A \cup B$ such that $|e \cap A| \in \{1, 2\}$. Note that $\chi(H)=2$, since we can colour all vertices in $A$ red and all vertices in $B$ blue. On the other hand, since every subset of size $2$ is contained in some hyperedge, the largest independent set has size $1$. Thus, $j(H)=2n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.