# A weak version of the Erdös-Faber-Lovasz conjecture

A hypergraph is a pair $H=(V,E)$ where $V$ is a nonempty set, and $E\subseteq {\cal P}(V)\setminus\{\emptyset\}$ is a collection of non-empty subsets of $V$.

Strong colorings. If $\kappa$ is a cardinal and $H=(V,E)$ is a hypergraph, we call a map $c:V\to \kappa$ a strong coloring if for all $e\in E$ the restriction $c|_e$ to $e$ is injective (that is, for any edge $e$, its members get all different colors).

Weak colorings. If $\kappa$ is a cardinal and $H=(V,E)$ is a hypergraph, we call a map $c:V\to \kappa$ a weak coloring if for all $e\in E$ with $|e|>1$ the restriction $c|_e$ to $e$ is non-constant (that is, for any edge $e$ with more than $1$ element, the elements of $e$ do not all receive the same color).

For any positive integer $n\in\mathbb{N}$ we say $H=(V,E)$ is an $n$-Erdös-hypergraph if $|E|=n$, and $|e| < n$ for all $e\in E$, and $|e_1\cap e_2| \le 1$ for $e_1\neq e_2\in E$.

A version of the Erdös-Faber-Lovasz conjecture states:

Any $n$-Erdös-hypergraph $H=(V,E)$ has a strong coloring $c:V\to \{0,\ldots,n-1\}$.

This conjecture has been open for more than 40 years.

Question. Does any $n$-Erdös-hypergraph $H=(V,E)$ have a weak coloring $c:V\to \{0,\ldots,n-1\}$?

Yes, and we do not even use the restrictions on mutual intersections of edges. For weak colorings, we may replace each edge with at least 2 vertices to an edge with exactly 2 vertices (possibly we get the same edge several times). It remains to properly color a graph with $n\geqslant 2$ edges with $n$ colors. This is done by induction: color any vertex of any edge in a color $n-1$, remove the edges incident to this vertex and proceed.
Moreover, if $c$ is a positive integer such that $c(c+1)/2\geqslant n+1$, then $c$ colors suffice. Indeed, if not, we may find a subgraph with all degrees at least $c$ (obtained by consecutive removing the vertices with degree less than $c$), it has at least $c+1$ vertices, thus at least $c(c+1)/2>n$ edges, a contradiction.