Resultados de complejidad sobre gráficos localmente bipartitos

Un gráfico es localmente bipartito si la vecindad abierta de cada vértice induce un gráfico bipartito. (Según las búsquedas, el mismo nombre podría usarse para otra cosa relacionada con las superficies).

¿Qué problemas de NP-hard para gráficos generales se convierten en polinomios para gráficos localmente bipartitos y cuáles permanecen NP-hard?

Especialmente interesado en camarilla y coloración.

¿Hay inclusiones entre localmente bipartito y otras clases de gráficos?

Agregado Según un documento , también se les llama "casi bipartitos" y sus complementos son gráficos lineales generalizados que no tienen garras.

Los gráficos localmente bipartitos obviamente contienen los gráficos localmente independientes (= sin triángulo). De acuerdo con graphclasses.org , la mayoría de los problemas de gráficos estándar ya son NP completos para gráficos sin triángulos y, por lo tanto, también NP completos para gráficos bipartitos locales. Las dos excepciones son camarilla (que obviamente es polinomial para gráficos localmente bipartitos porque la camarilla máxima es un triángulo) y cubierta de camarilla, que es polinomial para gráficos libres de triángulos pero podría ser más difícil para gráficos localmente bipartitos.

$\mathsf{NP}$$G$$H$$G$$\theta(G) = \beta(H)$$\theta$$\beta$$\mathsf{NP}$ buen resultado).