Graph Colorings – Chromatic Number and Taking Duals of Hypergraphs

graph-coloringshypergraphinfinite-combinatoricslo.logicset-theory

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

Best Answer

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

Related Question