Originator(s): P. Erdos, ?. Faber, L. Lovasz
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 Erdos-Faber-Lov\'asz 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 introduced the linear intersection number of a graph, which provides another formulation of the conjecture.
Comments/Partial results: Chang and Lawler [1988] proved that the edge-chromatic number of a simple n-vertex hypergraph is at most \ceil{3n/2}-2. Kahn 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 proved a fractional version of Conjecture 1, showing that the fractional chromatic number of such a graph is n.
References:
Chang W.I. and Lawler E. Edge coloring of hypergraphs and a conjecture of
Erdos, Faber, and Lovasz. Combinatorica 8 (1988), 293-295.
Erdos P. On the combinatorial problems I would most like to see
solved. Combinatorica 1 (1981), 25-42.
Kahn J. On some hypergraph problems of Paul Erdos and the asymptotics of
matching, covers and covering. The Mathematics of Paul Erdos
(Springer-Verlag, 1997), 345-371.
Kahn J. and Seymour P. A fractional version of the
Erdos-Faber-Lovasz Conjecture. Combinatorica 12 (1992), 155-160.
Klein H. and Margraf M. On the linear intersection number of graphs.
http://arxiv.org/PS_cache/math/pdf/0305/0305073.pdf