二部图的最优边着色

Question

我遇到了以下问题:在二分图中找到最优边着色。我知道贪婪着色算法有时不能返回最优的颜色数。“贪婪着色算法”的意思是:首先选择度最高的顶点，然后在颜色1...degree上对其边缘进行着色，然后选择具有<=度的顶点，再将其在第一个可用数(邻域不使用的最低数目)上的每个入射边着色，选择下一个顶点等。

但我引入了一个修改:第一选择顶点I颜色的边按降序(度.1)排列，以及下一个顶点的边，就像以前在1...degree上那样。这次修改的结果是我举了一些例子，我得到了最佳的颜色数。但我不太确定这是不是一条规则。有人知道这个版本的边着色算法是最优的，还是有人能够显示任何反例？

Answer 1

您可以将反例作为“天真”贪婪算法的反例，并将其转化为“复杂的”贪婪算法的反例。只需插入具有适当程度的虚拟节点即可“吸收”向后的颜色。人们总是可以在图的任意部分构建一个具有度n的新节点:只需在另一部分插入n新节点，并将每个节点通过单个边缘连接到所需的新节点。

由于所有按降序着色的节点都是新插入的，原来反例中的所有节点都按升序着色，因此得到了与原来的“朴素”贪婪算法相同的颜色。由于最优着色的颜色至少与原图的颜色相同，且新插入的节点都比原图的最大度小，所以新图不需要比原图更多的颜色。因此，由“复杂”算法产生的着色--它的颜色仍将超过原始图形所需的颜色--对于新的图形来说并不是最优的。

例如，以下面注释中描述的图形为例，左边有节点B、C、D，右边是E、F、G、H。它有以下几个边：

B connects to E, F, and G
C connects to E, F, and G
D connects to G and H

目前，我将假设您所接触的第一个节点按降序着色。(对于其他节点，甚至不清楚“降序”可能意味着什么--从哪个最大值下降？节点的程度可能不够高。)

因此，我们在左边插入一个新的节点A，在右边插入三个节点I、J和K；现在连接性是

A connects to I, J, and K
B connects to E, F, and G
C connects to E, F, and G
D connects to G and H

因此，复杂的贪婪算法会将AI-3、AJ-2、AK-1颜色化，然后在剩余的节点上继续作为朴素贪婪算法。