The [Erdös-Faber-Lovasz conjecture](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture) and [Hadwiger's conjecture](http://en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29) 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](http://arxiv.org/pdf/math/0305073v1.pdf) 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$. 



Implication between Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture?
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\}$.


