弦图笔记

· · 个人记录

弦图，没有证明。

前置知识：\omega(G),\chi(G),\kappa(G),\alpha(G)

分别对应：最大团，最小染色，最小团覆盖，最大独立集

有 \omega(G)\le\chi(G),\alpha(G)\le\kappa(G)

弦图：一个无向图称为弦图，当且仅当图中任意长度大于 3 的环都至少有一个弦。

对于弦图 G，有 \chi(G)=\omega(G)。

单纯点：这个点与它的邻居构成一个团。

任何一个弦图都至少有两个单纯点。不是完全图的图至少有一对单纯点满足它们不相邻。

完美消除序列：每次删去一个单纯点，直到删完。

一个无向图是弦图，当且仅当它有完美消除序列（PEO）。

求完美消除序列的算法有很多，这里只写一种：MCS 算法。

设 l_i 表示第 i 个点的邻居中有几个已放入完美消除序列，每次找到未放入序列中的 l_i 最大的点，将它倒序放入序列，并更新 l_i。使用链表维护 l_x=i 的 x 可以做到线性时间复杂度。

判断一个序列在图上是否是完美消除序列，只需看对于 v_i，它之后的与它相邻的点为 v_{c_1},v_{c_2},\cdots v_{c_k}，v_{c_1} 是否与其它的点都相邻。时间复杂度 \mathcal O(n+m)。

基于上述两个算法，我们可以在线性时间复杂度内解决弦图判定问题。

弦图的色数就是 k+1 的最大值。

对于一个团，必然只会有一个点在最大独立集中，所以在完美消除序列上贪心选择即可。

弦图属于完美图，也就是说，它的每一个诱导子图 H 都满足 \omega(H)=\chi(H)。这是很好理解的，毕竟弦图的诱导子图还是弦图，而弦图自己就满足这个特点。

例题：小朋友 神奇的国度