Pewarnaan planar yang tidak tepat dengan ukuran komponen monokromatik

Mari kita rilekskan sedikit pewarnaan, yaitu, kita memungkinkan sejumlah kecil simpul yang berdekatan diberi warna yang sama. Komponen monokromatik didefinisikan sebagai komponen yang terhubung dalam subgraph yang disebabkan oleh set simpul yang menerima warna yang sama, dan pertanyaannya adalah untuk menanyakan jumlah minimum warna yang diperlukan untuk mewarnai grafik sehingga komponen monokromatik terbesar memiliki ukuran tidak lebih dari . $\lambda$$C$
Pewarnaan tradisional dapat dianggap sebagai -warna dalam pengaturan ini. Oleh karena itu untuk menemukan jumlah minimum adalah NP-hard untuk grafik planar secara umum. $[\lambda,1]$$\lambda$

Pertanyaan saya adalah, bagaimana -warna grafik planar , atau lebih umum, -warna untuk ?$[\lambda,2]$$[\lambda,C]$$C \geq 2$

Hal ini dapat dilihat sebagai masalah ganda dari apa yang dipelajari oleh Edwards dan Farr , di mana adalah tetap, dan satu diminta untuk menemukan ukuran minimum .$\lambda$$C$

Pencocokan sempurna 2-warna dalam grafik planar kubik sangat mirip dengan masalah Anda yang dinyatakan sebagai NP-lengkap oleh Schaefer dalam makalah teorema dikotomi yang terkenal meskipun ia tidak memberikan bukti untuk grafik planar kubik. Masalahnya meminta keberadaan dua pewarnaan grafik planar kubik sedemikian rupa sehingga setiap simpul memiliki tepat satu tetangga dengan warna yang sama dengan dirinya sendiri.

EDIT: Pewarnaan yang rusak adalah versi keputusan dari masalah Anda. Grafik adalah (k, d) -warna jika seseorang dapat mewarnai simpul dengan warna k sedemikian sehingga tidak ada simpul yang berdekatan dengan lebih dari d simpul dengan warna yang sama. Masalah keputusan (2,1) -warna dengan cacat, yang setara dengan masalah optimisasi Anda, ditunjukkan sebagai NP-complete bahkan untuk grafik planar .