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.

  • $\begingroup$ Beautiful - thanks for this additional remark!! (Unfortunately I can only press +1 once.) I was wondering how much your upper bound goes up if we allow the intersections of the edges to be arbitrarily big: mathoverflow.net/questions/287068/… $\endgroup$ – Dominic van der Zypen Nov 27 '17 at 10:15
  • 1
    $\begingroup$ Yes, we never use it actually. $\endgroup$ – Fedor Petrov Nov 27 '17 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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