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

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .