Linear intersection number and vertex covering number 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:


*

*for $e\in L$ we have $|e|\geq 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$. (For infinite graphs, this concept is boring: $\ell(G) = |V(G)|$ for infinite graphs.)
For any graph $G$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$. 
Does $\tau(G) \leq \ell(G)$ hold for all graphs $G$?
 A: No, it might not hold.
Let $\pi=K_{4,4}$, so $|X|=8$ and each $e\in L$ contains exactly two vertices.
This implies that $\ell(G_\pi)\le 8$.
But for each $x\in X$ we must select at least three of the four edges meeting there in any vertex cover of $G_\pi$, thus $\tau(G_\pi)\ge 3\cdot 8/2=12$.
A: Let $H$ be a graph on $n$ vertices, thought of as the hypergraph in the question.  Then a vertex cover in $G_H$ is precisely a subgraph of $H$ that contains all but at most one edge at each vertex of $H$.  Such a subgraph is obtained from $H$ by deleting a subgraph of maximum degree at most $1$, which contains at most $n/2$ edges.  So any graph $H$ with more than $3n/2$ edges will provide a counterexample.
A: This answer is incorrect!
As pointed out by Ben, I confused dominating set and vertex cover.
Yes, it is true.
For every vertex $v$ of the hypergraph $\pi$, consider the edges of the graph $G$ that run between hyperedges that intersect in $v$.
This will be a clique, which we can denote by $K_v$.
We can select any vertex of the clique for each $v$, this gives a vertex cover of size at most "$\ell$".
The linearity seems not needed.
It would imply, btw, that any two such cliques are edge-disjoint, that is, $K_v\cap K_u\cap E=\emptyset$.
Therefore in this case the edgeset of the graph, $E$, is an edge-disjoint union of cliques.
