algorithm - 边缘着色算法中构造扇形时如何处理未着色的边缘

Question

我在实施 Misra & Gris 边缘着色算法时遇到问题。我有一个简单的问题 - 如何在最大风扇的构造中处理未着色的边缘？

uncolored 是所有顶点上的免费颜色，仅在未着色的顶点上免费（我们将 uncolored 视为单独的颜色）还是以其他方式？

Answer 1

显然这并不重要（在仔细阅读所有证明并编写代码之后）。然而，使用未着色的边缘可能会意外地使边缘不着色，因此需要在此类设置中对其进行跟踪。在这种情况下，最大风扇也会更大。