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

حدس اردوش–فابر–لوواس ( به انگلیسی: Erdős–Faber–Lovász conjecture ) یک مسئله بسیار عمیق و مهم در بحث رنگ آمیزی گراف ها در نظریه گراف ها است.
این نظریه بیان می کند که: اجتماع k کپی از k دسته که هر ۲ دستهٔ متمایز دلخواه حداکثر در یک راس اشتراک دارند دارای عدد رنگی k است. حداد و تاردیف در سال ۲۰۰۴ این نظریه را به بیان دیگری و با مطرح کردن یک مثال از کمیته های موجود در دانشگاه ارائه کردند: فرض کنید در یک دانشکدهٔ دانشگاه k کمیته وجود دارد و هر کدام هم شامل k نفر از اعضای هیئت علمی هستند و قرار است که همهٔ کمیته ها در یک اتاق با هم جلسه داشته باشند که در اتاق k صندلی وجود دارد. همچنین فرض کنید که اشتراک هر ۲ کمیتهٔ متمایز دلخواه شامل ۱ نفر می شود. آیا ممکن است که اعضای کمیته ها را به صندلی هایی نسبت دهیم به طوری که هر عضو در همه کمیته هایی که عضو آن ها است روی صندلی ثابتی بنشیند؟
پال اردوش ابتداً مبلغ ۵۰ دلار برای اثبات این حدس به عنوان جایزه قرار داده بود ولی بعداً آن را به مبلغ ۵۰۰ دلار افزایش داد. [ ۱] بهترین نتیجهٔ یافته شده تا به امروز این است که عدد رنگی این مسئله حداکثر k + o ( k ) [ ۲] است.
اگر مسئله را راحت تر و با شرایط کمتری در نظر بگیریم، بدین صورت که اجازه دهیم دسته ها در هر چند راسی که می خواهند، اشتراک داشته باشند؛ آنگاه عدد رنگی این نوع گرافها حداکثر 1 + k k − 1 خواهد شد. [ ۳]