绝大度为2的无往图的绝小染色数?

匿名用户 2018-08-12 94
Give a linear algorithm to compute the chromatic number of graphs where each vertex has degree at most 2. Must such graphs be bipartite? 求做法求证明 谢谢 题目来源:《算法设计手册》
其他回答
首先最大度为2的连通块只有3种
1. 点
2. 链
3. 环
对于点,只要1种颜色
对于链,只要2种颜色
对于奇数环,需要3种颜色
对于偶数环,只要2种颜色

其中奇数环存在时,并不是bipartite graph
证明还是比较简单的,题主自行证明吧
热心网民 2018-08-12 17:22:18 0条评论