0
$\begingroup$

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$?

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .