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


1 Answer 1


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\ge4$ and $\lambda\ge4$, 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=3$, let $H=K_3$.

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

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

If $\kappa\ge4$ and $\lambda=3$, let $H=K_\kappa\cup K_3$.

If $\kappa=3$ and $\lambda\ge4$, let $H=K_3\cup K_\lambda^\partial$.


Your Answer

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

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