فرض کنید گرافی ۲۱ راس دارد که ۱۹ راس درجه ۴ و۲راس از درجه ۳ است مینیمم تعداد رنگ برای رنگ آمیزی یال های گراف به طوری که هردو یال متصل رنگ های متفاوت داشته باشندچند است؟ پوران گفته ۵ تاولی راه حل را نگفته!
سلام. درکل بستگی به گرافش داره. ولی در بدترین حالت زیرگراف k6 نداریم که به ۶ رنگ نیاز داشته باشه (چون اصلاً راس از درجه ۵ نداره). یعنی تمام گرافهای با این مشخصات به بیشتر از ۵ رنگ نیاز ندارن. البته میشه یه گرافی با همین مشخصات ساخت که بشه با ۳ رنگ رنگش کرد.