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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.