The Erdős-Faber-Lovász Conjecture (1972)

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)$.

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.

[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.