ErdősFaberLovász conjecture: a simple hypergraph on \(n\) vertices has chromatic index at most \(n\)
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)uniform hypergraph, or \( r\)graph, for short, is a hypergraph whose edge set consists of \( r\)subsets of \( V\). A graph is just a special case of an \( r\)graph with \( r=2\).
We say that a hypergraph \( H\) (with vertex set \( V\)) is simple if no two edges of \( H\) have more than one vertex in common. In order to avoid trivialities, we will assume \( H\) has no singleton edges. By the chromatic index \( \chi'(H)\) of \( H\), we mean the least integer \( t\) such that there is a \( t\)coloring of the edges of \( H\) with the property that intersecting edges have distinct colors. One of Erdös' favorite combinatorial problems is the (by now) classic [3]:
Erd\H{osFaberLovász conjecture} [3], 1972 ($500)
Any simple hypergraph \(H\) on \(n\) vertices has chromatic index at most \(n\).An equivalent formulation is the following [2]:
Let \( G_1, \dots, G_n\) be \( n\) edgedisjoint complete graphs on \( n\) vertices. Then the chromatic number of \( \cup_{i=1}^n G_i\) is \( n\).
There is yet another nice equivalent formulation:
Let \( A_1, \ldots, A_n\) denote \( n\) sets each of size \( n\). Suppose \( \vert A_i \cap A_j\vert \leq 1\) for \( i \not = j\). Then the elements can be colored in \( n\) colors such that each set \( A_i\) consists of elements of distinct colors.
Erdös liked to tell the story that when the authors first came up with the conjecture, they were sure that it must be trivial. They soon realized that it was going to be harder than they thought. Now, more than 25 years later, it seems they were right  it is harder than they initially thought.
Observe that the upper bound of \( n\) can be achieved, eg., when \( H\) is a projective plane or a complete graph on \( n\) vertices with \( n\) odd. Kahn [5] has recently shown that the conjecture is asymptotically correct by proving that
If \( H\) is a simple hypergraph on \( n\) vertices, then
Kahn's proof actually gives
For an excellent survey of the research spawned by this (and several earlier) hypergraph conjectures of Erdös and his coauthors, the reader is directed to the insightful paper of Kahn [6].
Erdös also asked the question of determining \( \cup_{i=1}^n G_i\) if we require that \( G_i \cap G_j\), \( i \not = j\), is trianglefree, or should have at most one edge.
Bibliography  

1  C. Berge. On the chromatic index of a linear hypergraph and the Chvátal conjecture. Combinatorial Mathematics,
Proc. 3rd Int'; Conf. (New York, 1985), Ann. N. Y. Acad. Sci. 555, New York 1989, 4044.

2  M. Deza, P. Erdös and P. Frankl. Intersection properties of systems of finite sets. Proc. London Math. Soc. (3) 36 (1978) no. 2, 369384.

3 
P. Erdös,
Problems and results in graph theory and combinatorial
analysis, Graph theory and related topics (Proc. Conf., Univ.
Waterloo, Waterloo, Ont., 1977), 153163, Academic Press, New
YorkLondon, 1979.

4  Z. Füredi. The chromatic index of simple hypergraphs. Graphs and Combinatorics 2 (1986), 8992.

5 
J. Kahn,
Coloring nearlydisjoint hypergraphs with \( n+o(n)\) colors,
J. Comb. Theory Ser. A 59 (1992), 3139.

6 
J. Kahn, On some hypergraph problems of Paul Erdös and the asymptotics
of matchings, covers and colorings,
The Mathematics of Paul Erdös, I (R. L. Graham and J.
Nešetril, eds.), 345371, SpringerVerlag, Berlin, 1996.
