Skip to main content
added 663 characters in body
Source Link

EDIT: My original answer (below) is correct but not really optimal. This is easier: simply well-order the set of vertices and greedily color them using the well-ordering. More precisely, if you reach a vertex $v$ and have already colored all vertices appearing before $v$ in the well-ordering, color $v$ with the smallest ordinal that does not create a monochromatic edge with what has been done before. Since $v$ is contained in at most $|E|$ edges, there are at most $|E|$ forbidden colors, so the range of this coloring is at most $|E| + 1$. Thus, $\chi(H) \leq |E| + 1$ (or, sometimes better, the maximum degree of the hypergraph plus 1).

Original answer: No, this is impossible. It is always the case that $\chi(H) \leq |E|$ (or at least $\chi(H) \leq 2|E|$ if $E$ is finite). To see this, note that it's easy to define an injective partial function $c_0$ from a subset of $V$ to $|E|$ (or $2|E|$ if $E$ is finite) such that, for all $e \in E$, we have $|\mathrm{dom}(c_0) \cap e| \geq 2$ (simply enumerate the edges in order type $|E|$ and take care of them one at a time). Then any extension of $c_0$ to a function $c:V \rightarrow |E|$ will be a hypergraph coloring of $H$.

No, this is impossible. It is always the case that $\chi(H) \leq |E|$ (or at least $\chi(H) \leq 2|E|$ if $E$ is finite). To see this, note that it's easy to define an injective partial function $c_0$ from a subset of $V$ to $|E|$ (or $2|E|$ if $E$ is finite) such that, for all $e \in E$, we have $|\mathrm{dom}(c_0) \cap e| \geq 2$ (simply enumerate the edges in order type $|E|$ and take care of them one at a time). Then any extension of $c_0$ to a function $c:V \rightarrow |E|$ will be a hypergraph coloring of $H$.

EDIT: My original answer (below) is correct but not really optimal. This is easier: simply well-order the set of vertices and greedily color them using the well-ordering. More precisely, if you reach a vertex $v$ and have already colored all vertices appearing before $v$ in the well-ordering, color $v$ with the smallest ordinal that does not create a monochromatic edge with what has been done before. Since $v$ is contained in at most $|E|$ edges, there are at most $|E|$ forbidden colors, so the range of this coloring is at most $|E| + 1$. Thus, $\chi(H) \leq |E| + 1$ (or, sometimes better, the maximum degree of the hypergraph plus 1).

Original answer: No, this is impossible. It is always the case that $\chi(H) \leq |E|$ (or at least $\chi(H) \leq 2|E|$ if $E$ is finite). To see this, note that it's easy to define an injective partial function $c_0$ from a subset of $V$ to $|E|$ (or $2|E|$ if $E$ is finite) such that, for all $e \in E$, we have $|\mathrm{dom}(c_0) \cap e| \geq 2$ (simply enumerate the edges in order type $|E|$ and take care of them one at a time). Then any extension of $c_0$ to a function $c:V \rightarrow |E|$ will be a hypergraph coloring of $H$.

Source Link

No, this is impossible. It is always the case that $\chi(H) \leq |E|$ (or at least $\chi(H) \leq 2|E|$ if $E$ is finite). To see this, note that it's easy to define an injective partial function $c_0$ from a subset of $V$ to $|E|$ (or $2|E|$ if $E$ is finite) such that, for all $e \in E$, we have $|\mathrm{dom}(c_0) \cap e| \geq 2$ (simply enumerate the edges in order type $|E|$ and take care of them one at a time). Then any extension of $c_0$ to a function $c:V \rightarrow |E|$ will be a hypergraph coloring of $H$.