**Originator(s):** P. Erdős, ?. Faber, L. Lovász

**Definitions:**
A hypergraph is *linear* if no two edges share more than one vertex.
A proper *n*-edge-coloring of a hypergraph assigns colors from an
*n*-set to the edges so that edges sharing a vertex have distinct colors.

**Conjecture 1:**
The union of *n* pairwise edge-disjoint complete graphs
with *n* vertices is *n*-colorable.

**Conjecture 2:**
Every *n*-vertex linear hypergraph
without edges of size 1 is properly *n*-edge-colorable.

**Background/motivation:**
It is not hard to show that these two conjectures are equivalent; both are
known as the Erdős-Faber-Lovász Conjecture. The hypergraph
statement seems more natural than graph version. The graph statement is posed
as a way to express the hypergraph conjecture in more widely familiar language
of graph coloring.

When all the edges have size 2, Conjecture 2 reduces to Vizing's Theorem.
The condition becomes the statement that the hypergraph is a simple
*n*-vertex graph, which has maximum degree at most *n-1*, and
hence by Vizing's Theorem it is *n*-edge-colorable.

Klein and Margraf [KM] introduced the *linear intersection number* of a
graph, which provides another formulation of the conjecture.

**Comments/Partial results:**
Chang and Lawler [CL] proved that the edge-chromatic number of a simple
*n*-vertex hypergraph is at most *⌈3n/2⌉-2*.
Kahn [K] proved an asymptotic version of the conjecture, showing for Conjecture
2 that there is always a proper *n(1+o(1))*-edge-coloring.
Vu conjectured a stronger statement than
Kahn's asymptotic result.

Kahn and Seymour [KS] proved a fractional version of Conjecture 1, showing that
the fractional chromatic number of such a graph is *n*.
Another recent partial result appears in [JSW].

R. Dharmarajan and D. Ramachandran asked whether the conjecture can be extended
to a union of complete graphs of arbitrary sizes. That is, if the largest
of *p* complete graphs has *n* vertices, and *n≥p*, then is
the union always *n*-colorable?

**References:**

[CL] Chang W.I. and Lawler E.; Edge coloring of hypergraphs and a conjecture of
Erdős, Faber, and Lovász. Combinatorica 8 (1988), 293-295.

[E] Erdős P.; On the combinatorial problems I would most like to see
solved. Combinatorica 1 (1981), 25-42.

[JSW] Jackson, B; Sethuraman, G.; Whitehead, C.;
A note on the Erdős-Faber-Lovász conjecture.
Discrete Math. 307 (2007), no. 7-8, 911--915.

[K] Kahn J.; On some hypergraph problems of Paul Erdős and the
asymptotics of matching, covers and covering. *The Mathematics of Paul
Erdős* (Springer-Verlag, 1997), 345-371.

[KS] Kahn J. and Seymour P.; A fractional version of the
Erdős-Faber-Lovász Conjecture. Combinatorica 12 (1992), 155-160.

[KM] Klein H. and Margraf M.; On the linear intersection number of graphs.
http://arxiv.org/PS_cache/math/pdf/0305/0305073.pdf

updated 07/21/08