Erdős–Faber–Lovász conjecture

An instance of the Erdős–Faber–Lovász conjecture: a graph formed from four cliques of four vertices each, any two of which intersect in a single vertex, can be four-colored.

In graph theory, the Erdős–Faber–Lovász conjecture (1972) is a very deep problem about the coloring of graphs. It says:

The union of k copies of k-cliques intersecting in at most one vertex pairwise is k-chromatic.

Paul Erdős originally offered US$50 for proving the conjecture in the affirmative, and later raised the reward to US$500. It is easy to show that the desired chromatic number is less than $1+k{\sqrt {k-1}}$, and it was shown by Kahn that the chromatic number is at most $k+o(k)$.

See also

• Erdős conjecture

References

• Erdős, Paul (1981), "On the combinatorial problems I would most like to see solved", Combinatorica, 1: 25–42.

• Haddad, L.; Tardif, C. (2004), "A clone-theoretic formulation of the Erdös-Faber-Lovasz conjecture" (PDF), Discussiones Mathematicae Graph Theory, 24: 545–549

• Kahn, Jeff (1992), "Coloring nearly-disjoint hypergraphs with n + o(n) colors", Journal of Combinatorial Theory, Series A, 59: 31–39.

• Kahn, Jeff; Seymour, Paul D. (1992), "A fractional version of the Erdős-Faber-Lovász conjecture", Combinatorica, 12 (2): 155–160, doi:10.1007/BF01204719.

• Klein, Hauke; Margraf, Marian (2003), On the linear intersection number of graphs, arXiv:/ 0305073 math.CO / 0305073.

• Romero, David; Sanchez-Arroyo, Abdon (2007), "Advances on the Erdős–Faber–Lovász conjecture", in Grimmet, Geoffrey; McDiarmid, Colin (eds.), Combinatorics, Complexity, and Chance : A Tribute to Dominic Welsh, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, pp. 285–298.