1
$\begingroup$

This is a follow-up of an older question.

Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak coloring if for all $e \in E$ the restriction $c|_e$ is not constant. We call $c$ a strong coloring, if for all $e \in E$ the restriction $c|_e$ is injective. We let $\chi_w(H)$ be the smallest cardinal such that there is a weak coloring to that cardinal, and we define $\chi_s(H)$ similarly for strong colorings.

Suppose that $V$ is infinite and that there is an integer $n\in\mathbb{N}$ such that $1<|e|\leq n$ for all $e\in E$. Is it possible that $\chi_w(H)$ is finite, but $\chi_s(H)$ is infinite?

$\endgroup$
4
$\begingroup$

Of course. Let $V$ be a set of non-zero integers, and $E$ consists of triples $(a,b,c)$ such that not all $a,b,c$ have the same sign. That is, the sign is a weak 2-colouring. On the other hand, for a strong colouring all elements must have different colours, since each pair of vertices is contained in a triple from $E$.

$\endgroup$

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.