Colouring

顶点的着色把顶点分成不同的集合，所以着完色后，这些集合之间的边的性质决定了着色的性质。

比如bipart是用分成两个集合，边的性质是：任何一个边的两个端点分别在不同的集合里。

但是并不是所有的图都可以这样把顶点集合分成两部分，使得没有两个相邻顶点的颜色相同。一般的着色问题是，至少需要把顶点分成几部分？

1) 贪心算法：a) 把图的节点排序，颜色排序。 b) 给第$i$个节点着色的时候检查它所有已经着色的邻居找到最小的没被用过的颜色，用这个颜色
分析：如果一个节点的degree为d，那么遍历颜色最坏的情况是前d个颜色都被用了，只能用第d+1个颜色。从整个图来看，图的最大degree给使用的颜色(chromatic number)一个上界$\Delta+1$

n个委员会，其中可能有重复的成员，安排他们开会，显然不能有重复成员的委员会被安排到同一天开会，问题：找到最小的天数使得每个委员会都能开一次会。模型是以每个委员会为顶点，以有重复成员的关系为边画一个图，找出图的chromatic number。