**Originators:**
Paul Erdős, Vance Faber, László Lovász
(presented by Drew Onderko - REGS 2012)

**Definitions:**
A *proper coloring* of a graph $G$ is an assignment of colors to vertices
such that adjacent vertices receive different colors. The *chromatic
number* of $G$, denoted $\chi(G)$, is the least number of colors in a
proper coloring of $G$. A hypergraph $H$ is *linear* if any two edges
share at most one vertex; it is *$k$-uniform* if every edge has size $k$.
A *loop* is an edge of size $1$. A *strong coloring* of a hypergraph
is an assignment of colors to vertices such that no edge contains two vertices
of the same color (the usual definition of proper coloring requires only that
no edge be monochromatic). The *strong chromatic number* of a hypergraph
is the least number of colors in a proper coloring. A *proper
edge-coloring* of $H$ is an assignment of colors to edges such that
intersecting edges have different colors. The *chromatic index* of $H$,
denoted $\chi'(H)$, is the least number of colors in a proper edge-coloring of
$H$.

**Conjecture:**
Each of the following equivalent statements is true.

(Version 1) If $G$ is the union of $n$ edge-disjoint copies of $K_n$, then
$\chi(G) = n$.

(Version 2) If $H$ is a linear $n$-uniform hypergraph with $n$ edges, then the
strong chromatic number of $H$ is $n$.

(Version 3) If $H$ is a linear hypergraph with no repeated loops, then
$\chi'(H)$ is at most the number of vertices.

(Version 4) If $H$ is a linear hypergraph with $n$ vertices such that (i) every
two vertices lie together in some edge and (ii) there are exactly $n$
distinct loops, then $E(H)$ decomposes into $n$ partitions of $V(H)$.

**Comments:**

Partial results are as follows. Assume Version 3 unless otherwise stated.

[H] The conjecture holds for $n \le 10$.

[CC] The conjecture holds for cyclic Steiner 2-designs (which are essentially
uniform linear hypergraphs whose edges can be grouped into orbits).

[S] There exist at least $\frac{n}{m}$ pairwise disjoint edges, where $n$ and
$m$ are the numbers of vertices and edges. This result was motivated by the
EFL conjecture and is implied by the conjecture.

[Fu] The conjecture holds if every two edges of $H$ intersect.

[K] $\chi'(H) \le n + o(n)$ for linear $H$.

[KS] A fractional version of the conjecture holds.

[S] The conjecture holds if $\delta(H) > \sqrt{n}$ (under Version 2).

[Fa] For fixed uniformity there can exist only a finite number of
counterexamples to the conjecure on the class of hypergraphs that are linear,
uniform, and regular. Additionally, any counterexample on this class of
hypergraphs must exist between dense and sparse values.

See [RS] for a survey of many of the above results.

**References:**

[CC] Charles J. Colbourn; Marlene J. Colbourn; The chromatic index of cyclic
Steiner 2-designs. Intern. J. Math. and Math. Sci. 5 (1982), no. 4, 823-825.

[Fa] Vance Faber; The Erdős-Faber-Lovász conjecture: the uniform
regular case. J. Combin. 1 (2010), no. 2, 113-120.

[Fu] Z. Füredi; The chromatic index of simple hypergraphs. Graphs and
Combin. 2 (1986), no. 1, 89-92.

[H] N. Hindman; On a conjecture of Erdős, Faber, and Lovász about
*n*-colorings. Canad. J. Math. 33 (1981), 563-570.

[K] Jeff Kahn; Coloring nearly-disjoint hypergraphs with $n+o(n)$ colors.
J. Combin. Theory Ser. B 59 (1992), no. 1, 31-39.

[KS] Jeff Kahn; P. D. Seymour; A fractional version of the
Erdős-Faber-Lovász conjecture. Cominatorica 12 (1992), no. 2, 155-160.
for dense hypergraphs. Discrete Math. 308 (2008), no. 5?6, 991?992.

[RS] D. Romero; A. Sánchez-Arroyo; Advances on the
Erdős-Faber-Lovász conjecture. In Grimmet, Geoffrey; McDiarmid,
Colin, *Combinatorics, Complexity, and Chance: A Tribute to Dominic
Welsh*, Oxford Lecture Series in Mathematics and Its Applications, Oxford
University Press, (2007) pp. 285-298.

[S] Abdón Sánchez-Arroyo; The Erdős-Faber-Lovász conjecture

[S] P. D. Seymour; Packing nearly-disjoint sets. Combinatorica 2 (1982), no. 1,
91-97.