2
$\begingroup$

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).
$\endgroup$
4
  • 2
    $\begingroup$ What if $G$ is a triangle, and $V_1,V_2$ are couples of its vertices? $\endgroup$ Commented Apr 28, 2018 at 13:16
  • 1
    $\begingroup$ You probably meant $[V_i]^2\cap [V_j]^2\cap E =\emptyset $ ? $\endgroup$ Commented Apr 28, 2018 at 13:52
  • $\begingroup$ Correct, @max, will correct this $\endgroup$ Commented Apr 28, 2018 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$ Commented Apr 28, 2018 at 16:01

1 Answer 1

5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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