Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász (Q1112832)

A conjecture of Erdős, Faber, Lovász states that given n sets \(A_ 1,A_ 2,...,A_ n\), with \(| A_ i| =n\) for \(1\leq i\leq n\), and \(| A_ i\cap A_ j| \leq 1\) for \(1\leq i<j\leq n\), one can color the elements of \(\cup A_ i\) with n colors so that for each i no two elements of \(A_ i\) have the same color. Given a hypergraph \(H=(V,E)\), let us define the size of an edge \(e\in E\) as the number of vertices to which e is incident. H is called simple if for any pair u, v of distinct vertices in H there is at most one edge incident to both u and v, and H contains no edges of size one. The conjecture of Erdős, Faber and Lovász is equivalent to the statement that for any simple hypergraph H on n vertices, the chromatic index of H is at most n. In this paper it is proved that for any simple hypergraph H on n vertices, the chromatic index of H is at most \(\lceil 1.5n-2\rceil\), which implies that \(\lceil 1.5n-2\rceil\) colors suffice for the element-coloring problem of Erdős, Faber, Lovász.