색상 당 정점 수에 제한을 둘 수있는 그래프 색상 지정 알고리즘이 있습니까

Question

그래프 채색이 NP 완전 문제라는 것을 알고 있습니다. 주어진 색상을 가질 수있는 꼭지점 수에 제한을 추가하면 문제가 더 간단 해지는지 궁금합니다. 나는 이것을하는 알고리즘을 찾을 수없는 것 같다. 예를 들어 그래프가있는 경우 "이 그래프의 색상이 가장 작 으면 각 색상의 정점이 최대 3 개가됩니다."또는 문제를 단순화하는 경우 "이 그래프에 색상을 지정하는 방법이 있습니까? 각 색상마다 최대 3 개의 꼭지점이있는 4 가지 색상 "?

감사합니다.

Answer 1

이 문제는 원래의 그래프 착색 문제를 간단히 줄이면 NP 완성입니다. 그래프가 k 색으로 채색 될 수 있고 더 많은 색이 할당되지 않은 경우에만 n 노드 그래프가 k 색 가능합니다 n 노드보다. 다른 말로하면, 당신이 말하고있는 문제의 일반적인 버전은 특별한 경우로 그래프 색을 가지기 때문에 여전히 NP 하드 일 것입니다.

희망이 도움이됩니다.

Answer 2

나는 제한 주어진 그래프의 색 수를보고 있다고 것이라는 K 착색 쉽게 정확한 DSATUR 기반 알고리즘 [Randall-Brown 72][San Segundo 11] 첨가 한 정점이되어야 할 때 검색 공간 치기 될 수있는 assfined color k. 어쨌든 문제는 NP에 남아 있습니다.