دوستعلی مژده

فرض کنید ) G = (V, Eیک گراف ساده باشد. در این پروژه، رنگ آمیزی-مکانی همسایه )همسایه محل-رنگ آمیزی گراف های دلخواه( و رنگ آمیزی -٢فاصله ای دو موضوع مورد مطالعه است. روی گراف های حاصل ضرب دکارتی دو گراف، رنگ آمیزی مکان-همسایه ها و رنگ آمیزی -٢فاصله ای به طور دقیق بررسی می شوند. به علاوه روی حاصل ضرب لغت نامه ای، حاصل ضرب مستقیم و حاصل ضرب ریشه ای دو گراف رنگ آمیزی -٢فاصله ای مورد بررسی قرار می گیرد. منظور از رنگ آمیزی مکان-همسایه از گراف Gیک افراز از رئوس ) V (Gبه -kزیرمجموعه مستقل راسی }Π = {S١, S٢, . . . , Sk است به طوری که برای هر جفت از رئوسی متمایز uو vبا رنگ یکسان ،iیک کلاس رنگ دیگر Sjموجود باشد ) (j ̸= iکه یکی از آن ها همسایه ای در Sjدارد و دیگری چنین همسایه ای در Sjندارد. منظور از رنگ آمیزی -٢فاصله ای یک رنگ آمیزی از رئوس گراف Gاست به طوری که هر دو راس با فاصله حداکثر ،٢دارای رنگ های متمایز باشند