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

یک مثال از این حدس:یک گراف شامل ۴ دسته (گروه)که هر کدام دارای ۴ راس و هر ۲ دستهٔ متمایز دلخواه در یک راس مشترک باشند را می‌توان با ۴ رنگ، رنگ آمیزی کرد.

حدس اردیش–فابر–لوواش (به انگلیسی: Erdős–Faber–Lovász conjecture)‏ یک مسئله بسیار عمیق و مهم در بحث رنگ آمیزی گراف‌ها در نظریه گراف‌ها است.

این نظریه بیان می‌کند که: اجتماع k کپی از k دسته که هر ۲ دستهٔ متمایز دلخواه حداکثر در یک راس اشتراک دارند دارای عدد رنگی k است. حداد و تاردیف در سال ۲۰۰۴ این نظریه را به بیان دیگری و با مطرح کردن یک مثال از کمیته‌های موجود در دانشگاه ارایه کردند: فرض کنید در یک دانشکدهٔ دانشگاه k کمیته وجود دارد و هر کدام هم شامل k نفر از اعضای هیئت علمی هستند و قرار است که همهٔ کمیته‌ها در یک اتاق با هم جلسه داشته باشند که در اتاق k صندلی وجود دارد. همچنین فرض کنید که‌اشـتراک هر ۲ کمیتهٔ متمایز دلخواه شامل ۱ نفر می‌شود. آیا ممکن است که اعضای کمیته‌ها را به صندلی‌هایی نسبت دهیم به طوری که هـر عضو در همه کمیته‌هایی که عضو آنها است روی صندلی ثابتی بنشیند؟

پل اردیش ابتداً مبلغ ۵۰ دلار (دلار آمریکا) برای اثبات این حدس به عنوان جایزه قرار داده بود ولی بعداً آنرا به مبلغ ۵۰۰ دلار افزایش داد. بهترین نتیجهٔ یافته شده تا به امروز این است که عدد رنگی این مسئله حداکثر $k + o(k)$ است.

اگر مسئله را راحت‌تر و با شرایط کمتری در نظر بگیریم، بدین صورت که اجازه دهیم دسته‌ها در هر چند راسی که می‌خواهند، اشتراک داشته باشند؛ آنگاه عدد رنگی این نوع گرافها حداکثر $1 + k \sqrt{k - 1}$ خواهد شد.

جستارهای وابسته

حدس اردیش

منابع

«Erdős–Faber–Lovász conjecture.» Wikipedia, The Free Encyclopedia. ۲۵ May ۲۰۰۸, ۲۲:۰۶ UTC. Wikimedia Foundation, Inc. ۵ Jul ۲۰۰۸ <http://en.wikipedia.org/w/index.php?title=Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture&oldid=214918375>.