# Complexity results about locally bipartite graphs

A graph is locally bipartite if the open neighborhood of every vertex induces a bipartite graph. (According to searches the same name might be used for something else related to surfaces).

Which NP-hard for general graphs problems become polynomial for locally bipartite graphs and which remain NP-hard?

Especially interested in clique and coloring.

Are there inclusions between locally bipartite and other graph classes?

Added According to a paper they are also called "almost bipartite" and their complements are generalized line graphs which are claw free.

## 2 Answers

Locally bipartite graphs obviously contain the locally independent (= triangle-free) graphs. According to graphclasses.org, most of the standard graph problems are already NP-complete for triangle-free graphs, and therefore also NP-complete for locally bipartite graphs. The two exceptions are clique (which is obviously polynomial for locally bipartite graphs because the maximum clique is a triangle) and clique cover, which is polynomial for triangle-free graphs but might be harder for locally bipartite graphs.

Elaborating on David Eppstein's answer, Clique Cover remains $\mathsf{NP}$-hard for locally bipartite graphs. Let $G$ be the line graph of a cubic triangle-free graph $H$. It is easy to see that $G$ is locally bipartite (in fact, the open neighbourhood of each vertex induces a perfect matching) and $\theta(G) = \beta(H)$, where $\theta$ is the clique covering number and $\beta$ is the vertex cover number. But then, just use the fact that Vertex Cover is $\mathsf{NP}$-hard for cubic triangle-free graphs (for example, by this nice result).