گروه علوم کامپیوتر- دانشکده علوم ریاضی- دانشگاه مازندران- بابلسرـ ایران
10.22034/csj.2023.184644
چکیده
در این مقاله، الگوریتمی برای رنگآمیزی همسایه- مکانیاب درختها ارایه گردیده است. رنگآمیزی گرافها و کاربردهای آن از مباحث اصلی و پر کاربرد گرافهاست. رنگآمیزی گرافها در دو حوزه رنگآمیزی گرهها و رنگآمیزی یالهای گراف مورد مطالعه قرار گرفته اند. در رنگآمیزی گرهها، در سالهای اخیر مفاهیم جدیدی از رنگآمیزی گرافها مانند "رنگآمیزی مکانیاب" و " رنگآمیزی همسایه- مکانیاب"، مطرح شده و مورد مطالعه قرار گرفتهاند. تخصیص اعضای مجموعه رنگ C={c1, c2, …, ck} به مجموعه گرههای یک گراف را یک k- رنگ آمیزی (مناسب) گوییم اگر و فقط اگر به هیچ زوج همسایهای رنگ یکسان اختصاص نیافته باشد. با اعمال محدودیتهای بیشتر در رنگآمیزی، به انواع دیگری از این مسئله خواهیم رسید. تعداد حداقل رنگ برای رنگآمیزی مناسب یک گراف را عدد رنگی گراف گوییم؛ این عدد برای انواع رنگآمیزی به طور مشابهی تعریف میشود. پیدا کردن عدد رنگی یک گراف در فرم بهینهسازی مسئله و همچنین تشخیصk-رنگ پذیری گراف برای k>2، در فرم تصمیم مسئله، از مسایل معروف np-hard هستند. نوع خاصی از رنگآمیزی مناسب که موضوع این مقاله است، رنگآمیزی همسایه- مکانیاب گرهها است. در این مسئله گرهها باید طوری رنگآمیزی شوند که علاوه بر غیر یکسان بودن رنگ همسایهها، مجموعه رنگ همسایههای گرههای همرنگ، متمایز از هم باشند. در مبحث رنگآمیزی همسایه- مکانیاب گرهها با وجود مطالعات وسیع صورت گرفته در زوایای نظری بحث، از جمله روابط بین عدد رنگی در انواع رنگآمیزیها و عدد رنگی گرافهای خاص، از نظر الگوریتمی، در این زمینه نتیجه قابل توجهی وجود ندارد. در این مقاله، الگوریتمی برای رنگآمیزی همسایه- مکانیاب درختها ارایه شده است. ثابت میکنیم الگوریتم از مرتبه زمانی چند جملهای است و در مورد حداکثر رنگهای استفاده شده برای حالتهای خاصی از درختها بحث خواهیم کرد.
West, D.B.: Introduction to graph theory, vol. 2. Prentice hall Upper Saddle River (2001)
Chartrand, G., Erwin, D., Henning, M., Slater, P., Zhang, P.: The locatingchromatic number of a graph. Bull. Inst. Combin. Appl. 36, 89 – 101 (2002)
Slater, P.J.: Leaves of trees. In: Proceedings of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. 14, pp. 549–559 (1975)
Alcon, L., Gutierrez, M., Hernando, C., Mora, M., Pelayo, I.M.: Neighbor-locating colorings in graphs. Theoretical Computer Science 806, 144–155 (2020)
Slater, P.J.: Dominating and reference sets in a graph. Journal of Mathematical and Physical Sciences 22(4), 445–455 (1988)
A. Mojdeh. On the conjectures of neighbor locating coloring of graphs. Theoretical Computer Science, 922:300–307, 2022.
Karpovsky, M.G., Chakrabarty, K., Levitin, L.B.: On a new class of codes for identifying vertices in graphs. IEEE transactions on information theory 44(2), 599–611 (1998)
Moret, B.M.E., Shapiro, H.D.: On minimizing a set of tests. SIAM Journal on Scientific and Statistical Computing 6(4), 983–1003 (1985)
Chlebus, B.S., Nguyen, S.H.: On finding optimal discretizations for two attributes. In: Proceedings of the First International Conference on Rough Sets and Current Trends in Computing. vol. 1424, pp. 537–544. Springer Berlin Heidelberg, Berlin, Heidelberg (1998)
