عدد گراندی – بازی در گراف ها

یک گراف G=(V,E) داده شده، به رنگ ها، یک عدد تخصیص می دهیم، دو بازیکن الیس و باب رئوس به نوبت برای رنگ آمیزی انتخاب می کنند بطوریکه رنگ هر راس کوچکترین عدد طبیعی باشد که دو راس مجاور همرنگ نباشند. هدف آلیس مینیمم کردن تعداد کل رنگ های استفاده شده و هدف باب ماکسیمم کردن آن است. گراندی – بازی برای G ، تعداد رنگ های استفاده شده در بازی است به طوری که هر دو بازیکن، بهترین استراتژی را استفاده می کنند. در این مقاله ثابت شده که ماکسیمم بازی – عدد گراندی از جنگل 3 است و بازی عدد کروماتیک همگراف ها، از بازی عدد گراندی بیشتر است.

کلیدواژه ها:

عدد گراندی – بازی ، بازی رنگ آمیزی ، درخت