چکیده: این رساله به مطالعه نوع خاصی از رنگ آمیزی‎ با عنوان رنگ آمیزی مجموع‎ ‎ می‌پردازد. ‏هدف اصلی در این مسئله یافتن کمینه‌ی ممکن برای مجموع رنگ ها ( اعداد طبیعی ) در بین رنگ آمیزی‌های مجاز است. بطور کلی دو دیدگاه در برخورد با این مسئله وجود داشته است. رویکرد تحلیلی و رویکرد الگوریتمی. رویکرد اصلی این رساله در بررسی این مسئله بیشتر متوجه دیدگاه دوم است. در این راستا یکی از روش‌های فرا ابتکاری برای این مسئله ‎NP-سخت، روش جستجوی همسایگی متغیر است. برای افزایش سرعت جستجوی همسایگی‌ها، از مفهوم جدیدی بنام نگهدارندگی استفاده شده‌است. بعد از پیاده سازی این روش برای مسئله رنگ آمیزی مجموع، کارایی آن روی چند نمونه گراف مورد بررسی و مقایسه قرار گرفته‌است. همچنین ارایه دو مفهوم مجموع رنگی راسی تفاضلی و جمعی به عنوان دو تعمیم برای مجموع رنگی راسی گراف، موضوعی است که در این رساله مورد توجه قرار گرفته‌است. شرایط عدم وجود همریختی بین دو گراف و یافتن کران برای عدد رنگی کسری از جمله نتایج این دو مفهوم جدید است.