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$. (For infinite graphs, this concept is boring: $\ell(G) = |V(G)|$ for infinite graphs.)

For any graph $G$ let $\text{col}(G) = \sup\{\delta(H): H\subseteq G\}+1$, where $\delta(\cdot)$ denotes the minimal degree. We have $\chi(G) \leq \text{col}(G)$ for all finite graphs $G$.

Is there a graph $G$ such that $\text{col}(G) > \ell(G)$?

  • $\begingroup$ What happens if you replace the colouring number with the minimum degree $+1$, or the maximum degree $+1$, or the chromatic number? $\endgroup$ – Andrew D. King Mar 5 '15 at 23:43
  • $\begingroup$ If you replace the colouring number with the chromatic number, the question is equivalent to the Erdos-Faber-Lovasz conjecture (en.wikipedia.org/wiki/…) -- see arxiv.org/abs/math/0305073 $\endgroup$ – Dominic van der Zypen Mar 6 '15 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.