در این مقاله، الگوریتمی برای رنگ آمیزی همسایه-مکان یاب درختها ارایه گردیده است. رنگ آمیزی گرافها و کاربردهای آن از مباحث اصلی و پر کاربرد گرافهاست. رنگ آمیزی گرافها در دو حوزه رنگ آمیزی گره ها و رنگ آمیزی یالهای گراف مورد مطالعه قرار گرفته اند. در رنگ آمیزی گره ها، در سالهای اخیر مفاهیم جدیدی از رنگ آمیزی گرافها مانند "رنگ آمیزی مکان یاب" و " رنگ آمیزی همسایه-مکان یاب"، مطرح شده و مورد مطالعه قرار گرفته اند. تخصیص اعضای مجموعه رنگ C={c_1,c_2,…,c_k} به مجموعه گره های یک گراف را یک k-رنگ آمیزی( مناسب) گوییم اگر و فقط اگر به هیچ زوج همسایه ای رنگ یکسان اختصاص نیافته باشد. با اعمال محدودیتهای بیشتر در رنگ آمیزی، به انواع دیگری از این مساله خواهیم رسید. تعداد حداقل رنگ برای رنگ آمیزی مناسب یک گراف را عدد رنگی گراف گوییم؛ این عدد برای انواع رنگ آمیزی به طور مشابهی تعریف می شود. پیدا کردن عدد رنگی یک گراف در فرم بهینه سازی مساله و همچنین تشخیص k-رنگ پذیری گراف برای k>2 ، در فرم تصمیم مساله، از مسایل معروف np-hard هستند. نوع خاصی از رنگ آمیزی مناسب که موضوع این مقاله است، رنگ آمیزی همسایه-مکان یاب گره ها است. در این مساله گره ها باید طوری رنگ آمیزی شوند که علاوه بر غیر یکسان بودن رنگ همسایه ها، مجموعه رنگ همسایه های گره های همرنگ، متمایز از هم باشند. در مبحث رنگ آمیزی همسایه-مکان یاب گره ها با وجود مطالعات وسیع صورت گرفته در زوایای نظری بحث، از جمله روابط بین عدد رنگی در انواع رنگ آمیزی ها و عدد رنگی گرافهای خاص، از نظر الگوریتمی، در این زمینه نتیجه قابل توجهی وجود ندارد. در این مقاله، الگوریتمی برای رنگ آمیزی همسایه-مکان یاب درختها ارایه شده است. ثابت می کنیم الگوریتم از مرتبه زمانی چند جمله ای است و در مورد حداکثر رنگهای استفاده شده برای حالتهای خاصی از درختها بحث خواهیم کرد.
