1
$\begingroup$

Motivation. If $\kappa\neq\emptyset$ is a cardinal, then a simple, undirected graph $G=(V,E)$ is $\kappa$-colorable if and only if there is a partition of $V$ into at most $\kappa$ blocks such that every edge $e\in E$ intersects $2$ blocks.

$\kappa$-colorability of a hypergraph. Let $H=(V,E)$ be a hypergraph, that is $V$ is a set and $E\subseteq {\cal P}(V)$. If $\kappa \neq \emptyset$ is a cardinal, we say that a map $c:V\to \kappa$ is a (hypergraph) coloring if for every $e\in E$ with $|e|>1$ the restriction $c|_e$ is non-constant.

$\kappa$-partitionability of a hypergraph. If $H=(V,E)$ is a hypergraph and $\kappa\neq\emptyset$ is a cardinal, we say that $H$ is $\kappa$-partitionable if there is a partition of $V$ into at most $\kappa$ blocks such that for every $e\in E$ with $|e|>1$ we have that $e$ is not a subset of any block of the partition.

It is easy to see that if $H$ is $\kappa$-partitionable, then it is $\kappa$-colorable (just give every block a different color). Does the converse hold?

$\endgroup$
  • $\begingroup$ If the answer is "Yes", then this could be the motivation for the fact that the requirement that a coloring be non-constant on non-singleton edges (instead of injective). $\endgroup$ – Dominic van der Zypen Feb 3 at 7:26
  • 4
    $\begingroup$ How is a partition functionally different from a coloring? Gerhard "If You Label, It Isn't" Paseman, 2020.02.03. $\endgroup$ – Gerhard Paseman Feb 3 at 8:01
  • $\begingroup$ Oh right, via pre-images, I suppose... $\endgroup$ – Dominic van der Zypen Feb 3 at 8:46

Your Answer

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

Browse other questions tagged or ask your own question.