Erdős–Faber–Lovász conjecture

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.^[1] The best known result to date is that the chromatic number is at most <math>k + o(k)</math>.^[2] If one relaxes the problem, allowing cliques to intersect in any number of vertices, the chromatic numbers of the resulting graphs are at most <math>1 + k \sqrt{k - 1}</math>, and some graphs of this type require this many colors.^[3]

See also

• Erdős conjecture

Notes

References