Erdős–Faber–Lovász conjecture

From Wikipedia, the free encyclopedia

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.^[1] The best known result to date is that the chromatic number is at most $k + o (k)$ .^[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 $1 + k \sqrt{k - 1}$ , and some graphs of this type require this many colors.^[3]

[edit] See also

Erdős conjecture

[edit] 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, MR 0963120, DOI 10.1007/BF02126801 .

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, MR 0602413, DOI 10.1007/BF02579174 .

Erdős, Paul (1991), “Advanced problem 6664”, American Mathematical Monthly 98 (7): 655, <http://www.jstor.org/view/00029890/di991764/99p03452/0> . 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”, Discussiones Mathematicae Graph Theory 24: 545–549, MR 2120637, <http://www.rmc.ca/academic/math_cs/tardif/paper25/paper25.pdf> .

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

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, MR 1141320, DOI 10.1016/0097-3165(92)90096-D .

Kahn, Jeff & Seymour, Paul D. (1992), “A fractional version of the Erdős-Faber-Lovász conjecture”, Combinatorica 12 (2): 155–160, MR 1179253, DOI 10.1007/BF01204719 .

Klein, Hauke & Margraf, Marian (2003), On the linear intersection number of graphs, arXiv: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, Combinatorics, Complexity, and Chance : A Tribute to Dominic Welsh, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, pp. 285–298 .