# Hypergraphs with edge coloring number equalling number of vertices

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.

• This seems related to the Erdos-Faber-Lovasz conjecture en.wikipedia.org/wiki/… – Gil Kalai Feb 4 '17 at 20:49
• Won't any finite projective plane work? (Btw, this seems to be the answer to many of your questions on MO ;) – domotorp Feb 4 '17 at 20:57
• 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? – Dominic van der Zypen Feb 5 '17 at 8:50