2
$\begingroup$

If $H=(V,E)$ is a hypergraph and $\kappa\neq \emptyset$ is a cardinal, then a map $c:V\to \kappa$ is said to be a colouring if for every edge $e\in E$ with $|e|\geq 2$ the restriction $c\restriction_e: e\to \kappa$ is not constant. The smallest cardinal $\kappa$ for which there is a colouring $c:V \to \kappa$ is said to be the chromatic number of $H$ and is denoted by $\chi(H)$.

The dual of the hypergraph $H=(V,E)$ is $H^\partial = (E, E_V)$ where $$E_V = \big\{S\subseteq E: \text{there is }v_0\in V \text{ such that } S = \{e\in E: v_0\in e\}\big\}.$$

Question. Given cardinals $\kappa, \lambda \geq 2$, is there always a hypergraph $H$ with $\chi(H) = \kappa$ and $\chi(H^\partial) = \lambda$?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

If I understand correctly, $\chi(H^\partial)$ is the least number of colours which suffice to colour the edges of $H$ so that each vertex is incident with edges of at least two different colours. And it seems to me that $H$ is isomorphic to $(H^\partial)^\partial$ provided that, for any vertices $x,y\in V(H)$, there is an edge $e\in E(H)$ such that $|e\cap\{x,y\}|=1$. I believe the answer is affirmative for all $\kappa,\lambda\ge2$. Each of the example hypergraphs is either an ordinary graph, or the dual of a graph, or the disjoint union of a graph and the dual of a graph.

If $\kappa\ge4$ and $\lambda=2$, let $H=K_\kappa$ (the complete graph of order $\kappa$).

If $\kappa=2$ and $\lambda\ge4$, let $H=K_\lambda^\partial$.

If $\kappa\ge3$ and $\lambda\ge3$, let $H=K_\kappa\cup K_\lambda^\partial$ (disjoint union).

If $\kappa=2$ and $\lambda=2$, let $H=C_4$.

If $\kappa=3$ and $\lambda=2$, let $H=K_4-e$.

If $\kappa=2$ and $\lambda=3$, let $H=(K_4-e)^\partial$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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