علیرضا انعامی عراقی - دانشکده مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد فراهان، ایران
جواد اکبری ترکستانی - دانشکده مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد اراک
محمدرضا میبدی - دانشکده مهندسی کامپیوتر و فناوری اطلاعات دانشگاه صنعتی امیرکبیر تهر

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

مساله رنگآمیزی گراف، الگوریتمهای اکتشافی،اتاماتای یادگیر سلولی