本题目前唯一一篇题解里说对于 $K=0$ 的时候只需要三染色就能构造出最优解，但感觉可能不一定。

考虑一个变换：$(V,E)\rightarrow(V',E')$，其中 $V'=[1,3|V|]\cap \mathbf Z,E'=E\cup\{(u,v)|u=i,v=|V|+2i+c\ (i\in [1,|V|],v\in[1,2])\}$。

这相当于将每个点再连上两个儿子。

从 $(\{1\},\emptyset)$ 开始一直变换到某个，每次选择独立集肯定是选择最大的，选择个数大致为 $\frac 2 3 n,\frac 4 9 n\cdots$（不能选择旧点，否则删去旧点添加两个新点），这是 $O(\log n)$ 的，并不是 $6$ 个以内，况且还没有考虑额外边。

所以是我理解错了，还是题解错了，但数据过水？