Implication between Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture?

Question

The Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture can be stated in a very similar form:

Erdös-Faber-Lovasz conjecture: for all finite simple undirected graphs $G=(V,E)$ we have $\chi(G)\leq \ell(G)$ where $\ell(G)$ is the linear intersection number (which we define below). (This article shows why this is equivalent to the original statement.)

Hadwiger's conjecture: for all finite simple undirected graphs $G=(V,E)$ we have $\chi(G)\leq \eta(G)$ where $\eta(G)$ is the largest $n\in \omega$ such that $K_n$ is a minor of $G$.

Question: We would have an implication between the two conjectures if either $\ell(G) \leq \eta(G)$ for all graphs $G$ or $\ell(G) \geq \eta(G)$ for all graphs $G$. Does any of these inequalities hold for all graphs?

---

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:

1. for $e\in L$ we have $|e|\geq 2$;
2. if $e_1\neq e_2 \in L$ then $|e_1\cap e_2|\leq 1$.

We set $X(\pi)=X$ and $L(\pi)=L$. The graph $G_\pi$ associated to a linear hypergraph $\pi$ is given by $G=(V,E)$ where $V = L$ and $E = \{\{e_1, e_2\} \subseteq L: e_1\neq e_2\text{ and } e_1\cap e_2\neq \emptyset\}$. It turns out that for any graph $G$ there is a linear hypergraph $\pi$ such that $G\cong G_\pi$. For any graph $G$ the we set $$\ell(G) := \text{min}\{|X(\pi)|:\pi \text{ is a linear hypergraph such that } G_{\pi} \cong G\}$$ and call this the linear intersection number of $G$.

Answer 1

Unfortunately, neither $\ell(G) \leq \eta(G)$ holds for all graphs $G$, nor $\eta(G) \leq \ell(G)$ holds for all graphs $G$.

1. Example for a graph $G$ with $\ell(G)>\eta(G)$. Consider the graph $G=(V,E)$ where $V = \{0,1,2\}$ and $E = \big\{\{0,1\},\{1,2\}\big\}$. Clearly $K_3$ is not a minor of $G$, but $K_2$ is, so $\eta(G) = 2$. Also, it is easy to see we cannot construct a linear hypergraph $\pi$ on only $2$ points such that $G_\pi \cong G$, so $\ell(G) >2$.

2. Example for a graph $G$ with $\eta(G)>\ell(G)$. Let $S = \{0,1,2,3,4\}$ and let $V = \big\{\{a,b\}: a,b\in S, a\neq b \big\}$. We set $E = \big\{\{x,y\}: x,y\in V \text{ and } x\cap y \neq \emptyset\big\}$. Now let $G=(V,E)$. Clearly, $G$ itself is a linear hypergraph, constructed on the five points $S=\{0,\ldots,4\}$, so $\ell(G) \leq 5$. (Probably we can prove that $\ell(G) = 5$, but for the argument, only the inequality is important.) We want to show that $K_6$ is a minor of $G$ which then implies $\eta(G) > 5 \geq \ell(G)$. So we have to find 6 connected subsets of $G$ that are "connected to each other", that is there is an edge between every two of them. These 6 sets are:

   • $\big\{\{0,k\}\big\}$ for $k = 1,2,3,4$ -- these are already 4 (singleton) sets, so we have to add 2 more sets, but these are not singletons, but larger connected sets:
   • $\big\{\{1,2\},\{2,3\},\{3,4\}\big\}$, and
   • $\big\{\{1,3\},\{1,4\},\{2,4\}\big\}$.