چکیده: برای گراف ،Gتابع c : V (G) −→ ℵ را یک رنگ
آمیزی مجاز گوییم هرگاه برای هر (uv ∈ E(G داشته باشیم (c(u) ̸= c(v مجموع رنگی متناظر با رنگ
آمیزی c را برابر با (Σu∈V (G)c(u تعریف می
کنیم و مجموع رنگی ،Σ(G) ،G را کمترین مقدار ممکن برای مجموع رنگی، در میان همه
ی رنگ
آمیزی
های مجاز G قرار می
دهیم. همچنین کمترین تعداد رنگی که برای آن، می
توان یک رنگ
آمیزی، با مجموع رنگ یکسان با مجموع رنگی گراف G پیدا کرد را قدرت رأسی ،s(G) ،G می
نامیم. در این پایان
نامه، ابتدا با مرور بر تحقیقات گذشته، با روند ایجاد مسأله
ی مجموع رنگی و بسط و گسترش این مفهوم آشنا خواهیم شد و گستره
ی آن را در علومی نظیر مهندسی و الکترونیک، با بیان کاربردی از مسأله
ی »مجموع رنگی« که به مسأله
ی طراحی V LSI معروف است، نشان خواهیم داد. همچنین در ادامه مروری بر تعاریف اساسی و قضایای کلی مورد استفاده در فصل
های آینده خواهیم داشت. مفاهیم رنگ
آمیزی مینیمال، مجموع رنگی و قدرت رأسی گراف را در فصل سوم بیان، و به بررسی کران
هایی برای این مفاهیم خواهیم پرداخت. و در نهایت با استفاده از مفهوم هم ریختی گراف
ها، به ذکر کران
هایی برای مجموع رنگی می
پردازیم و فصل را با بیان دو الگوریتم، جهت محاسبه
ی تقریبی از مقادیر مجموع رنگی و قدرت رأسی، به پایان خواهیم رساند.