مسئله رنگ¬آمیزی رأسی گراف یک زمینه فعال تحقیق است که همراه با بسیاری از زیرمجموعه¬های جالب [4، 5، 6] و برنامه¬های کاربردی در زمینه¬هایی مانند زمان¬بندی، تخصیص فرکانس، برنامه¬ریزی و غیره [2] می¬باشد. مسئله رنگ¬آمیزی گراف به درستی رنگ کردن رئوس یک گراف با کوچکترین تعداد ممکن رنگ است، به طوری که هیچ دو رأس مجاور یکسان نباشند. اگر یک رنگ¬آمیزی با رنگ k وجود داشته باشد، گراف k-رنگ¬پذیر نامیده می¬شود. عدد رنگی یک گراف G به صورت) χ (G نشان¬دهنده حداقل تعداد رنگ برای رنگ¬آمیزی مناسب G است. عدد رنگی χ (G) چندجمله¬ای قابل محاسبه است، زمانی که
اما وقتی که
به مسئله NP-کامل تبدیل می¬شود، حتی برای گراف¬های G با درجه Δ (G) ≥ 3. در نتیجه، بسیاری سوالات پاسخ داده نشده مربوط به رنگ¬آمیزی گراف وجود دارد [5]. به دنبال الگوریتم¬های دقیق و استفاده از مجموعه¬های ماکسیمال مستقل برای محاسبه عدد رنگی، بیگل و همکارانش [1] روی یک الگوریتم مرتبه O(2.4151n) ایجاد شده است. پس از آن، بیسکوف [2] یک الگوریتم مرتبه O(2.4023n) ارائه کرد. هر دو الگوریتم دارای یک استراتژی بالا-پایین با استفاده از ترکیبی از مرزهای بالایی بهبود یافته در تعداد مجموعه¬های ماکسیمال مستقل (MIS) با اندازه بیشتر از k در یک رویکرد برنامه¬نویسی پویاست.
ما ابتکار جدیدی برای رنگ¬آمیزی گراف طراحی کرده¬ایم. با توجه به گراف ورودیG داده شده، ابتدا دورهای زوج و زیرگراف¬های غیردوری را از بین می¬بریم، زیرا آنها می¬توانند دو رنگ¬پذیر باشند. بر طبق نتایج حاصل از گراف، G1، این روش در هر تکرار یک Ki MIS ایجاد می¬کند و آن را از Gi جدا می¬کند، بنابراین یک زیرگراف
تشکیل می¬شود. این روش تا زمانی که یک زیرگراف 2-رنگ¬پذیر چندجمله¬ای –زمانی بدست آید، تکرار می-شود. آگاهی از مرزهای پایین برای عدد استقلال گراف ()(α (G) یک اندازه مناسب برای تعیین ویژگی¬های ترکیبی یک گراف است. در این مقاله، ما نشان می¬دهیم که α (G) اندازه منحصر بفرد مفیدی برای محاسبه χ (G) نیست. اگر G یک گراف همبند و K یک MIS از G باشد، ما اولین مرز پایین را روی ماکسیمال تعداد یال¬هایی که به گره¬های K وارد می¬شوند، تعیین می¬کنیم و نشان می¬دهیم که این مرز پایین، مرز جدید بالایی را ایجاد می¬کند. ما یک MIS Ki برای هر زیرگراف Gi ایجاد می¬کنیم که در تعداد یال¬های Gi که به گره¬های Ki وارد می¬شوند، صادق است، حداقل تعداد گره¬های فعلی منهای 1 است، یعنی