حدس اردوش–فابر–لوواس

یک مثال از این حدس:یک گراف شامل 4 دسته (گروه)که هر کدام دارای 4 راس و هر 2 دسته ی متمایز دلخواه در یک راس مشترک باشند را می توان با 4 رنگ، رنگ آمیزی کرد

در نظریه گراف ها حدس اردوس-فابر-لوواز یک مسئله بسیار عمیق و مــهم در بحث رنـگ آمـــیزی گراف ها است. این نظریه بیان می کند که : اجتماع k کپی از k دسته که هر 2 دسته ی متمایز دلخواه حداکثر در یک راس اشتراک دارند دارای عدد رنگی k است. حداد و تاردیف در سال 2004 این نظریه را به بیان دیگری و با مطرح کردن یک مثال از کمیته های موجود در دانشگاه ارایه کردند : فرض کنید در یک دانشکده ی دانشگاه k کمیـته وجود دارد و هر کـدام هم شامـل k نفر از اعضای هیئت علمی هستند و قرار است که همه ی کمیته ها در یک اتاق با هم جلسه داشته باشند که در اتــاق k صندلی وجود دارد. همچنین فرض کنید که اشــتراک هر 2 کمــیته ی متمایز دلخواه شامل 1 نفر می شود. آیا ممکن است که اعضای کمیته ها را به صندلی هایی نسبت دهیم به طوری که هـر عضو در همه کمیته هایی که عضو آنها است روی صندلی ثابتی بنشیند؟ پاول اردوس ابتداً مبلغ 50 دلار (دلار امریکا) برای اثبات این حدس به عنوان جایزه قرار داده بود ولی بعداً آنرا به مبلغ 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. 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, آرخیو:/ 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.