为图形着色，使每个节点都着色或与着色节点相邻

Question

假设您有一个连通的无向图 G。您希望 G 中的每个节点都被着色或与一个着色节点相邻。设计一种算法，为图 G 适当着色。您只能为 floor(n/2) 个节点着色，其中 n 是节点总数。

我尝试了一个解决方案，但我发现它并没有完全解决约束的问题，我想要推动或被告知我走错了路。

我的解决方案基本上是 运行 BFS，并每隔三分之一 "level" 为节点着色。但我发现了一个失败的实例——只是一个包含三个节点的链表。如果我为头部或尾部着色，那么其中一个节点将与着色节点的距离为 2，我不太确定如何保证中间节点将被着色。

Answer 1

选择一个根并使用 DFS 生成生成树。

然后为每个第 2 级的节点着色。选择为偶数级别或奇数级别着色，具体取决于哪种选择将为最少的节点着色。