اطلاعات مرتبط با تیتر زیر را جمع‌آوری کنید و یک خبر کوتاه بنویسید

تیتر: رنگبندی بخشی گراف
خبر:
رنگبندی بخشی (fractional coloring) رنگ‌بندی بخشی موضوعی جدید در شاخه تئوری گراف (graph theory) است که به نام تئوری گراف بخشی (fractional graph theory) شناخته می‌شود . این موضوع تعمیمی از رنگ‌بندی گراف معمولی می‌باشد . در رنگ‌بندی گراف سنتی ، هر رأس از گراف به رنگ‌های متعددی در آورده می‌شود و رأس‌های مجاور (به این معنا که به وسیلهٔ یالی به هم متصل شده‌اند) باید به رنگ‌های متمایزی در آورده شوند . در یک رنگ‌بندی بخشی ، یک مجموعه خاص از رنگ‌ها به هر رأس گراف نسبت داده می‌شود . در این مسئله هم رأس‌های مجاور نباید دارای رنگ‌های مشابه باشند . رنگ‌بندی بخشی را می‌توان به عنوان راحت‌سازی برنامه‌نویسی خطی یا (linear programming relaxation) در نظر گرفت .