ارائه یک راهکار جدید به منظور رنگ آمیزی رئوس گراف

مسئله رنگ آمیزی رئوس گراف ، یک مسئله بسیار مهم در تئوری گراف است که در آن به هر یکاز رئوس گراف یک رنگ اختصاص داده می شود ؛ بگونه ای که به هر دو رأس مجاور از گراف،رنگ های متفاوتی تخصیص داده شود و هیچیک از رئوس ، رنگ تکراری نداشته باشند. در سال-های اخیر راه حل ها و الگوریتم های موثر زیادی برای رنگ آمیزی گراف ها ارائه شده است. بهعنوان مثال جستجوی محلی و برنامه نویسی محلی که در آن با استفاده از کلاس IMPASSE ،رنگ آمیزی رئوس گراف به شکل قابل قبولی انجام خواهد شد. علاوه بر این راه حل می توان رئوسیک گراف را با روش بهینه و نیمه بهینه توسط عدد کروماتیک رنگ آمیزی کرد، ولی این روشبرای گراف های کوچک مناسب است و برای دسته خاصی از گراف ها از جمله گراف های کامل وبزرگ مناسب نیست. در این مقاله یک راهکار ترتیبی برای رنگ آمیزی گراف ارائه شده است کهدر آن رنگ آمیزی را به دو مرحله تقسیم می کند به نحوی که، یک مرحله ترتیب ورود رئوس ومرحله بعدی یک بازه حداقل و حداکثر برای رنگ آمیزی تعدادی از رئوس که، بیش از یک رنگبرای رنگ آمیزی آنها موجود می باشد در نظر گرفته شده است.

کلیدواژه ها:

جستجوی محلی ، رنگ آمیزی رئوس ، عدد کروماتیک ، کلاس IMPASSE