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


  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).
  • 2
    $\begingroup$ What if $G$ is a triangle, and $V_1,V_2$ are couples of its vertices? $\endgroup$ – Fedor Petrov Apr 28 '18 at 13:16
  • 1
    $\begingroup$ You probably meant $[V_i]^2\cap [V_j]^2\cap E =\emptyset $ ? $\endgroup$ – Max Apr 28 '18 at 13:52
  • $\begingroup$ Correct, @max, will correct this $\endgroup$ – Dominic van der Zypen Apr 28 '18 at 15:53
  • $\begingroup$ @FedorPetrov You are right - I forgot the requirement that $E \subseteq [V_1]^2 \cup \ldots \cup [V_n]^2$ $\endgroup$ – 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.


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.