3-Clique Partition dla wykresów o stałej średnicy

Problem podziału na 3 kliki polega na określeniu, czy wierzchołki wykresu, powiedzmy , można podzielić na 3 kliki. Problem ten jest trudny do wyeliminowania przez proste zmniejszenie z 3-kolorowego problemu. Nietrudno dostrzec, że odpowiedź na ten problem jest łatwa, gdy diam ( G ) = 1 lub diam ( G ) > 5 . Problem pozostaje trudny NP, gdy diam ( G ) = 2 przez zwykłą redukcję od siebie (biorąc pod uwagę wykres G , dodaj wierzchołek i połącz go ze wszystkimi innymi wierzchołkami).$G$$\textrm{diam}(G) = 1$$\textrm{diam}(G) > 5$$\textrm{diam}(G) = 2$$G$

Jaka jest złożoność tego problemu dla wykresów z dla 3 ≤ p ≤ 5 ?$\textrm{diam}(G) = p$$3\le p \le 5$

Problem wydaje się być w .$P$

Weź dwa wierzchołki , v z odległości dokładnie 3 (taka para musi istnieć, gdy p ≥ 3 ). Muszą mieć różne kolory (użyję R, G, B, aby oznaczyć 3 kolory, a wierzchołki tej samej kliki mają ten sam kolor). Wlog zakłada, że u ma kolor czerwony, a v ma kolor zielony.$u$$v$$p\ge 3$$u$$v$

$\Gamma(u)$$u$$\Gamma(v)$$V-\Gamma(u)-\Gamma(v)$$u$$v$$u$$v$$v$musi być w kolorze zielonym lub niebieskim. Każdy wierzchołek ma teraz co najwyżej dwie możliwości, dlatego problemem staje się instancja 2-SAT, którą możemy rozwiązać w czasie wielomianowym.