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

For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x,y \in X, x\neq y\big\}$.

Consider the following statement (S):

Statement (S) : Let $G=(V,E)$ be a finite undirected graph and $V_1, \ldots, V_n\subseteq V$ with the following properties:

• $V = V_1\cup\ldots\cup V_n$,
• $E \subseteq [V_1]^2 \cup \ldots \cup [V_n]^2$, that is every member of $E$ is "inside" some $V_i$,
• for $i\in\{1,\ldots,n\}$ we have $\chi(G_i) = n$ where $G_i = (V_i, E\cap [V_i]^2)$, and
• for $i\neq j\in\{1,\ldots,n\}$ we have $[V_i]^2\cap [V_j]^2 \cap E = \emptyset$, that is, $V_i$ and $V_j$ share no common edge.

Then we have $\chi(G) = n$.

(Statement (S) ends here.)

Questions.

1. Is (S) provably false?
2. If not, does the Erdös-Faber-Lovasz conjecture (EFL) imply (S)? Note that clearly (S) is a (possibly false) statement implying (EFL).
• What if $G$ is a triangle, and $V_1,V_2$ are couples of its vertices? – Fedor Petrov Apr 28 '18 at 13:16
• You probably meant $[V_i]^2\cap [V_j]^2\cap E =\emptyset$ ? – Max Apr 28 '18 at 13:52
• Correct, @max, will correct this – Dominic van der Zypen Apr 28 '18 at 15:53
• @FedorPetrov You are right - I forgot the requirement that $E \subseteq [V_1]^2 \cup \ldots \cup [V_n]^2$ – Dominic van der Zypen Apr 28 '18 at 16:01

It is false already for $n=2$. Take a 5-cycle 12345 and sets 123, 3451.