Erdős-Faber-Lovász Conjecture/1972

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?

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

Index Page; Glossary

updated 07/21/08