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, named after Paul Erdős, Vance Faber, and László Lovász. It says:

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

Haddad & Tardif (2004) introduce the problem with a story about seating assignment in committees: suppose that, in a university department, there are k committees, each consisting of k faculty members, and that all committees meet in the same room, which has k chairs. Suppose also that at most one person belongs to the intersection of any two committees. Is it possible to assign the committee members to chairs in such a way that each member sits in the same chair for all the different committees to which he or she belongs? In this model of the problem, the faculty members correspond to graph vertices, committees correspond to cliques, and chairs correspond to vertex colors.

Paul Erdős originally offered US$50 for proving the conjecture in the affirmative, and later raised the reward to US$500. The best known result to date is that the chromatic number is at most $k+o(k)$. If one relaxes the problem, allowing cliques to intersect in any number of vertices, the chromatic numbers of the resulting graphs are at most $1+k{\sqrt {k-1}}$, and some graphs of this type require this many colors.

See also

• Erdős conjecture

References

• Chiang, W. I.; Lawler, E. L. (1988), "Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász", Combinatorica, 8 (3): 293–295, doi:10.1007/BF02126801, MR0963120.

• Chung, Fan; Graham, Ron (1998), Erdős on Graphs: His Legacy of Unsolved Problems, A K Peters, pp. 97–99.

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

• Erdős, Paul (1991), "Advanced problem 6664", American Mathematical Monthly, 98 (7): 655, doi:10.2307/2324942. Solutions by Ilias Kastanas, Charles Vanden Eynden, and Richard Holzsager, American Mathematical Monthly 100 (7): 692–693, 1992.

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

• Hindman, Neil (1981), "On a conjecture of Erdős, Faber, and Lovász about n-colorings", Canad. J. Math., 33 (3): 563–570, MR0627643.

• Horák, P.; Tuza, Z. (1990), "A coloring problem related to the Erdős–Faber–Lovász conjecture", Journal of Combinatorial Theory, Series B, 50 (2): 321–322, doi:10.1016/0095-8956(90)90087-G. Corrected in JCTB 51 (2): 329, 1991, to add Tuza's name as coauthor.

• Kahn, Jeff (1992), "Coloring nearly-disjoint hypergraphs with n + o(n) colors", Journal of Combinatorial Theory, Series A, 59: 31–39, doi:10.1016/0097-3165(92)90096-D, MR1141320.

• 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, MR1179253.

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

• Romero, David; Sánchez Arroyo, Abdón (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.