Erdős–Faber–Lovász conjecture

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.

harvtxt|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. [harvtxt|Chung|Graham|1998.] The best known result to date is that the chromatic number is at most k + o(k). [harvtxt|Kahn|1992.] 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. [harvtxt|Erdős|1991; harvtxt|Horák|Tuza|1990.]

ee also

* Erdős conjecture

Notes

References


*citation
last1 = Chiang | first1 = W. I.
last2 = Lawler | first2 = E. L.
title = Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
journal = Combinatorica
volume = 8 | issue = 3 | year = 1988 | pages = 293–295 | doi = 10.1007/BF02126801
id = MathSciNet | id = 0963120.

*citation
last1 = Chung | first1 = Fan | authorlink1 = Fan Chung
last2 = Graham | first2 = Ron | authorlink2 = Ronald Graham
title = Erdős on Graphs: His Legacy of Unsolved Problems
year = 1998
publisher = A K Peters
pages = 97–99.

*citation
last=Erdős | first = Paul | authorlink = Paul Erdős
title = On the combinatorial problems which I would most like to see solved
journal = Combinatorica | year = 1981 | volume = 1 | pages = 25–42
id = MathSciNet | id = 0602413
doi = 10.1007/BF02579174.

*citation
last=Erdős | first = Paul | authorlink = Paul Erdős
title = Advanced problem 6664
journal = American Mathematical Monthly
url = http://www.jstor.org/view/00029890/di991764/99p03452/0
volume = 98 | issue = 7 | pages = 655 | year = 1991. [http://www.jstor.org/view/00029890/di991784/99p0942t/0 Solutions by Ilias Kastanas, Charles Vanden Eynden, and Richard Holzsager] , American Mathematical Monthly 100 (7): 692–693, 1992.

*citation
first1 = L. | last1 = Haddad
first2 = C. | last2 = Tardif
title = A clone-theoretic formulation of the Erdős-Faber-Lovasz conjecture
journal = Discussiones Mathematicae Graph Theory
volume = 24 | year = 2004 | pages = 545–549
url = http://www.rmc.ca/academic/math_cs/tardif/paper25/paper25.pdf
id = MathSciNet | id = 2120637.

*citation
last = Hindman | first = Neil
title = On a conjecture of Erdős, Faber, and Lovász about "n"-colorings
journal = Canad. J. Math.
volume = 33 | year = 1981 | issue = 3 | pages = 563–570
id = MathSciNet | id = 0627643.

*citation
last1 = Horák | first1 = P.
last2 = Tuza | first2 = Z.
title = A coloring problem related to the Erdős–Faber–Lovász conjecture
journal = Journal of Combinatorial Theory, Series B
volume = 50 | issue = 2 | year = 1990 | pages = 321–322
doi = 10.1016/0095-8956(90)90087-G. Corrected in [http://dx.doi.org/10.1016/0095-8956(91)90046-M JCTB 51 (2): 329, 1991] , to add Tuza's name as coauthor.

*citation
last = Kahn | first = Jeff
title = Coloring nearly-disjoint hypergraphs with "n" + "o"("n") colors
journal = Journal of Combinatorial Theory, Series A
year = 1992 | volume = 59 | pages = 31–39
doi = 10.1016/0097-3165(92)90096-D | id = MathSciNet | id = 1141320.

*citation
last1 = Kahn | first1 = Jeff
last2 = Seymour | first2 = Paul D. | authorlink2 = Paul Seymour (mathematician)
title = A fractional version of the Erdős-Faber-Lovász conjecture
journal = Combinatorica
volume = 12 | issue = 2 | year = 1992 | pages = 155–160
doi = 10.1007/BF01204719 | id = MathSciNet | id = 1179253.

*citation
last1 = Klein | first1 = Hauke
last2 = Margraf | first2 = Marian
title = On the linear intersection number of graphs
year = 2003
id = arxiv | math.CO | 0305073.

*citation
contribution = Advances on the Erdős–Faber–Lovász conjecture
last1 = Romero | first1 = David
last2 = Sánchez Arroyo | first2 = Abdón
title = Combinatorics, Complexity, and Chance : A Tribute to Dominic Welsh
editor1-last = Grimmet | editor1-first = Geoffrey
editor2-last = McDiarmid | editor2-first = Colin
series = Oxford Lecture Series in Mathematics and Its Applications
publisher = Oxford University Press
year = 2007 | pages = 285–298.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Erdős conjecture — The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects.Some of these are the following: * The Cameron–Erdős conjecture on sum free sets of integers, solved by… …   Wikipedia

  • List of things named after Paul Erdős — The following were named after Paul Erdős:* Erdős number * Erdős cardinal * Erdős conjecture a list of numerous conjectures named after Erdős ** Erdős conjecture on arithmetic progressions ** Cameron–Erdős conjecture ** Erdős–Burr conjecture **… …   Wikipedia

  • László Lovász — Infobox Scientist name = László Lovász caption = László Lovász speaking in 2007 at the EPFL birth date = Birth date and age|1948|3|9|mf=y birth place = Budapest, Hungary residence = Budapest, Hungary nationality = Hungarian, American ethnicity =… …   Wikipedia

  • Vance Faber — Infobox Scientist name = Vance Faber caption = birth date = Birth date and age|1944|12|1|mf=y birth place = Buffalo, New York residence = Seattle, Washington nationality = American ethnicity = field = Mathematician alma mater = Washington… …   Wikipedia

  • Problèmes non résolus en mathématiques — Ce qui suit est une liste de problèmes non résolus en mathématiques. Sommaire 1 Problèmes du prix du millénaire 2 Autres problèmes encore non résolus 2.1 Théorie des nombres 2.2 …   Wikipédia en Français

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”