A linear hypergraph is a pair $\pi=(\{1,\ldots,n\}, L)$ where $n\in\mathbb{N}$, $n\geq 2$ 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$.

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\}$.

The only examples of a linear hypergraph $\pi = (\{1,\ldots,n\},L)$ such that $\chi(G_\pi) = n$ that I am aware of are:

(1) $\pi$ is a so-called "near-pencil", this means, fix $j^*\in \{1,\ldots n\}$ and set $L = \big\{\{j^*,x \}: x\in \{1,\ldots,n\} \land x\neq j^*\big\}\cup \big\{\{1,\ldots,n\}\setminus \{j^*\}\big\}$

(2) $\pi$ is the line graph of $K_n$, or more precisely, $L = \big\{\{a,b\}: a,b\in \{1,\ldots n\} \land a< b\big\}$,

(3) $\pi=(\{1,\ldots,n\},L)$ is a projective plane.

Are there any other examples of a linear hypergraph $\pi = (\{1,\ldots,n\},L)$ such that $\chi(G_\pi) = n$?

Remark. Case (2) above only works for $n$ odd. The reason is that the edge chromatic number of $K_n$ equals $n-1$ for $n$ even, and it equals $n$ for $n$ odd.

  • $\begingroup$ This seems related to the Erdos-Faber-Lovasz conjecture en.wikipedia.org/wiki/… $\endgroup$ – Gil Kalai Feb 4 '17 at 20:49
  • 3
    $\begingroup$ Won't any finite projective plane work? (Btw, this seems to be the answer to many of your questions on MO ;) $\endgroup$ – domotorp Feb 4 '17 at 20:57
  • $\begingroup$ Right -- I forgot to mention that, will include it. Question is, are the three types, near-pencil, $L(K_n)$, and proj. plane the only ones? $\endgroup$ – Dominic van der Zypen Feb 5 '17 at 8:50

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.