چکیده: یک k-رنگ
آمیزی پویا برای گراف ،G یک k-رنگ
آمیزی مجاز از G است، به
طوری
که برای هر راس (v ∈ V (G که درجه آن حداقل ٢ است، حداقل دو رنگ متفاوت در همسایگی راس v ظاهر شده باشد. کوچکترین عدد صحیح k به
طوری
که، یک k-رنگ
آمیزی پویا از گراف G وجود داشته باشد عدد رنگی پویای G گویند و با χ٢(G) نمایش می
دهند. عدد رنگی و عدد رنگی پویای یک گراف می
توانند دارای اختلاف به اندازه دلخواه بزرگ باشند. مونت گومری در رساله دکتری خود مساله رنگ
آمیزی پویا را معرفی کرد، همچنین حدس زد که اختلاف عدد رنگی پویا و عدد رنگی گراف
های منتظم حداکثر ٢ است. این حدس توسط افراد زیادی مورد مطالعه قرار گرفته است. علیشاهی نشان داد اختلاف عدد رنگی پویا و عدد رنگی یک گراف k-منتظم به
صورت ( O(lnk است. همچنین او یک کران بالا برای عدد رنگی پویای گراف
های منتظم براساس عدد رنگی خود گراف و عدد استقلال توان دوم آن گراف معرفی کرد. در این پایان نامه سعی می
کنیم به ارتباط بین عدد رنگی و عدد رنگی پویای گراف
ها در حالت خاص بپردازیم. همچنین کران بالای عدد رنگی پویای بعضی از گراف
ها را مشخص می
کنیم، علاوه بر آن عدد رنگی پویای انتخابی (لیستی) را معرفی کرده و برخی از نتایج آن
را را بیان می
کنیم.