3-Clique Partition untuk grafik dengan diameter tetap

Masalah 3-Clique Partition adalah masalah menentukan apakah simpul dari sebuah grafik, misalnya , dapat dipartisi menjadi 3 klik. Masalah ini NP-hard dengan pengurangan sederhana dari masalah 3-colorability. Tidak sulit untuk melihat bahwa jawaban untuk masalah ini mudah ketika diam ( G ) = 1 atau diam ( G ) > 5 . Masalahnya tetap NP-keras ketika diam ( G ) = 2 dengan reduksi sederhana dari dirinya sendiri (diberi grafik G , tambahkan simpul dan hubungkan ke semua simpul lainnya).$G$$\textrm{diam}(G) = 1$$\textrm{diam}(G) > 5$$\textrm{diam}(G) = 2$$G$

Apa kompleksitas masalah ini untuk grafik dengan untuk 3 ≤ p ≤ 5 ?$\textrm{diam}(G) = p$$3\le p \le 5$

Masalahnya tampaknya dalam .$P$

Ambil dua simpul , v dengan jarak tepat 3 (pasangan seperti itu harus ada saat p ≥ 3 ). Mereka harus memiliki warna yang berbeda (saya akan menggunakan R, G, B untuk menunjukkan 3 warna dan simpul dalam klik yang sama diwarnai dengan warna yang sama). Wlog menganggap Anda berwarna Merah dan v berwarna Hijau.$u$$v$$p\ge 3$$u$$v$

$\Gamma(u)$$u$$\Gamma(v)$$V-\Gamma(u)-\Gamma(v)$$u$$v$$u$$v$$v$harus diwarnai Hijau atau Biru. Setiap simpul sekarang memiliki paling banyak dua pilihan, oleh karena itu masalahnya menjadi instance 2-SAT yang dapat kita selesaikan dalam waktu polinomial.