رنگ کردن یک گراف مسطح.

[amir.ekhlasi]

فرض کنید یک گراف مسطح داریم که یالهای آن پاره خطند و درجه هر رأس 3 است. یالهای این گراف را با سه رنگ r,g,b رنگ میکنیم. به طوری که هر رأس هر سه رنگ را داشته باشد. یک رأس را ساعتگرد مینامیم هرگاه یالهای آن از طرف ساعتگرد به شکل r-g-b رنگ شده باشند و پادساعتگرد مینامیم هرگاه برعکس باشد. ثابت کنید اختلاف تعداد رأسهای ساعتگرد با پادساعتگرد بر 4 بخشپذیر است.

 

[goodarz]

پاسخ : رنگ کردن یک گراف مسطح.

یه سوال, آیا همچین گرافی (گراف مسطح که یال هاش پاره خط باشن و درجه هر راس 3 باشه) وجود داره؟

 

[amir.ekhlasi]

پاسخ : رنگ کردن یک گراف مسطح.

دو تا n ضلعی تو هم که رأسهاش را به طور متناظر به هم وصل کردیم.