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.


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.