弦图

这里大概就是一些证明口胡

MCS证明还不会

设 A={x}+N(x),B={y}+N(y)，若 A⫋B ，则 A 不是极大团。此时在完美消除序列上显然有 y在 x 前。

设 nxt_x表示 N(x)中在完美消除序列上最靠前的点， y表示所有满足 A⊆B 的 y 中的最靠后的点。此时必然有 nxt_y=x，否则 y 不是最靠后的，令 y=nxt_y仍然满足条件。

假设构造方案使用了 \(t\) 种颜色，\(col_G\) 为最小染色数，则有 \(col_G\leq t\)

对于最大团的诱导子图，有 \(t\leq w_G\)，后者为最大团大小。如果该条不成立，可推的与最大团矛盾

然后又有 \(w_G\leq col_G\)，然后就证出来了。

显然对于任意独立集 \(p\) ，\(\sum p_i+N_{p_i}\) 为团覆盖，前者小于等于最大独立集，后者大于等于最小团覆盖

而最小团覆盖肯定大于等于最大独立集，然后就出来了。