<p>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 <a href="http://www.jaist.ac.jp/~uehara/pdf/triangle.pdf" rel="nofollow">this</a> nice result).</p>

CC BY-SA 3.0
2016-03-26T15:28:44.450Z
2016-03-26T15:28:44.450Z
Andrea M
<p>Locally bipartite graphs obviously contain the locally independent (= triangle-free) graphs. <a href="http://www.graphclasses.org/classes/gc_371.html">According to graphclasses.org</a>, 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.</p>

CC BY-SA 3.0
2015-01-16T19:07:51.327Z
2015-01-16T19:07:51.327Z
David Eppstein
<p>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).</p>

<blockquote>
  <p>Which NP-hard for general graphs problems become polynomial
  for locally bipartite graphs and which remain NP-hard?</p>
</blockquote>

<p>Especially interested in clique and coloring.</p>

<blockquote>
  <p>Are there inclusions between locally bipartite and other
  graph classes?</p>
</blockquote>

<hr>

<p><strong>Added</strong> According to a <a href="http://dimatia.fav.zcu.cz/files/files1996/27.ps" rel="noreferrer">paper</a> they are also called "almost bipartite" and their complements
are generalized line graphs which are claw free.</p>

<reference-request><graph-theory>
Complexity results about locally bipartite graphs
joro
# Complexity results about locally bipartite graphs

(Asked by: username_0 on 2015-01-16)

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](http://dimatia.fav.zcu.cz/files/files1996/27.ps) they are also called "almost bipartite" and their complements
are generalized line graphs which are claw free.

**Tags:** reference-request, graph-theory


---

## 2 answers

### Answer by username_2 on 2015-01-16. Score: 17 | Accepted answer

Locally bipartite graphs obviously contain the locally independent (= triangle-free) graphs. [According to graphclasses.org](http://www.graphclasses.org/classes/gc_371.html), 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.


---

### Answer by username_1 on 2016-03-26. Score: 3

Elaborating on username_2'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](http://www.jaist.ac.jp/~uehara/pdf/triangle.pdf) nice result).


---

