## DIMACS TR: 2001-40

## Characterization of superbipartite graphs

### Authors: I. E. Zverovich

**
ABSTRACT
**

Let $G$ and $H$ be graphs.
A {\em substitution} of $H$ in $G$ instead of a vertex $v \in V(G)$ is
the graph $G(v \to H)$, which consists of disjoint union of $H$ and $G - v$
with the additional edge-set $\{xy: x \in V(H), y \in N_G(v)\}$.
For a hereditary class of graphs ${\mathcal P}$,
the {\em substitutional closure} of ${\mathcal P}$ is defined
as the class ${\mathcal P}^*$ consisting of all graphs which can be obtained
from graphs in $P$ by repeated substitutions.

Let ${\mathcal B}$ be the class of all graphs $G$ such that
$G - N[v]$ is a bipartite graph for every vertex $v$ of $G$.
Here $N[v]$ denotes the closed neighborhood of $v$.
A graph is called a {\em superbipartite graph} if it is in the
substitutional closure of ${\mathcal B}$.

We characterize superbipartite graphs in terms of forbidden induced subgraphs.
Note that the weighted stability number in ${\mathcal B}^*$ can be
found in polynomial time.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-40.ps.gz

DIMACS Home Page