以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  06年极小非平面图点着色问题[原创][讨论]  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=79214)

--  作者：mafeichao
--  发布时间：12/18/2009 11:00:00 PM

--  06年极小非平面图点着色问题[原创][讨论]

题目：给极小非平面图顶点着色，
（1）至少需要几种颜色，为什么？
（2）至多需要几种颜色，为什么？

第一问容易理解
第二问采用四色定理证明容易理解，但是用五色定理不能理解
前辈们给出的参考答案说存在v，d(v) < 5，令G‘ = G-v是平面图，因而可5着色，然后回复成G，仿照五色定理证明的情况三讨论即可，但是我认为不能仿照情况三讨论，因为五色定理的证明回复G后，G仍为平面图，因而C1，3和C2，4只能一个存在，从而可以换色，但是这里回复G后却不是平面图了，因而C1，3和C2，4可能同时存在，这时还能换色吗？

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 31.250ms