→ k75715 :C 是裡面的 min odd-cycle 08/06 16:23
※ 引述《nendi (midi)》之銘言：
: Let G be a graph (simple and loopless)
: and every two odd cycles in G have a common vertex
: Prove (最小著色數) X(G) <= 5
: 在下的想法是對 odd cycle 的 number 用 induction 下去做
: 可是最後的odd cycle 一直不知道怎麼調整好
: 想麻煩知道的人給個方向
: 感謝
沒有odd-cycle的case 你一定會做~~
如果有odd-cycle 那你就考慮 G \ V(C)的圖的性質
然後再分別塗色 放回去 就結束啦~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.61.64