Hasil kerumitan tentang grafik bipartit lokal

Grafik adalah bipartit lokal jika lingkungan terbuka dari setiap simpul menginduksi grafik bipartit. (Menurut penelusuran, nama yang sama dapat digunakan untuk hal lain yang terkait dengan permukaan).

NP-hard untuk masalah grafik umum mana yang menjadi polinomial untuk grafik bipartit lokal dan yang tetap NP-hard?

Terutama tertarik pada klik dan pewarnaan.

Apakah ada inklusi antara bipartit lokal dan kelas grafik lainnya?

Ditambahkan Menurut sebuah makalah mereka juga disebut "hampir bipartit" dan komplemen mereka adalah grafik garis umum yang bebas cakar.

Grafik bipartit lokal jelas mengandung grafik yang independen secara lokal (= bebas segitiga). Menurut graphclasses.org , sebagian besar masalah grafik standar sudah NP-lengkap untuk grafik bebas segitiga, dan karenanya juga NP-lengkap untuk grafik bipartit lokal. Dua pengecualian adalah klik (yang jelas polinomial untuk grafik bipartit lokal karena klik maksimum adalah segitiga) dan penutup klik, yang polinom untuk grafik bebas segitiga tetapi mungkin lebih sulit untuk grafik bipartit lokal.

$\mathsf{NP}$$G$$H$$G$$\theta(G) = \beta(H)$$\theta$$\beta$$\mathsf{NP}$ hasil yang bagus).