چکیده: هدف این پایان
نامه بررسی یکی از حالت
های رنگ
آمیزی گراف
های ساده به
نام b-رنگ
آمیزی است. b-رنگ
آمیزی راس
های گراف را به مجموعه
هایی مستقل به نام کلاس
های رنگی طوری افراز می
کند، که در هر کلاس رنگی راسی وجود دارد که آن راس، در بقیه کلاس
های رنگی دارای همسایه باشد. در ادامه بزرگترین افراز را برای برخی گراف
های خاص مانند گراف
های کنسر با پارامترهای nو ، K(n, k)) ،k) گراف
های d-منتظم و گراف بدست آمده از حاصل
ضرب دکارتی دو گراف، را مورد مطالعه قرار می
دهیم. به عبارت دیگر ماکسیمم مقدار k که گراف G دارای b-رنگ
آمیزی با k رنگ باشد را مشخص می
کنیم و آن را عدد b-رنگی نامیده و با (φ(G نمایش می
دهیم.