## DIMACS TR: 2000-46

## Graph Bipartition with Hereditary Properties

### Authors: I. E. Zverovich

**
ABSTRACT
**

A hereditary class $P$ is called {\it finitely generated}
if the set of all minimal forbidden induced subgraphs for $P$ is finite.
For a pair of hereditary classes $P$ and $Q$, we define a hereditary
class $P * Q$ of all graphs $G$ which have a partition $A \cup B = V(G)$
such that $G(A) \in P$ and $G(B) \in Q$
($G(X)$ is the subgraph of $G$ induced by $X \subseteq V(G)$).
We investigate the problem of recognizing finitely generated classes
of the form $P * Q$.

We use the following model.
Let $H^0$ and $H^1$ be hypergraphs with the same vertex set $V$.
The ordered pair $H = (H^0, H^1)$ is called a {\em bihypergraph}.
A bihypergraph $H = (H^0, H^1)$ is called {\em bipartite} if there is an
ordered partition $V^0 \cup V^1 = V(H)$ such that $V^i$ is stable in
$H^i$, $i = 0, 1$.
If the maximum cardinality of hyperedges in $H$ is at most $r$ and every
$k$-subset of $V(H)$ contains at least one hyperedge then $H \in C(k, r)$.

We prove that there exists a finite number of minimal non-bipartite
bihypergraphs in $C(k, r)$ (when $k$ and $r$ are fixed).

Let $P$ and $Q$ be hereditary classes of graphs.
Suppose that the stability number $\alpha (H)$ is bounded above for all
$H \in P$, and the clique number $\omega (H)$ is bounded above for all
$H \in Q$.
An ordered partition $A \cup B = V(G)$ is called a {\it ramseian
$P * Q$-partition} if $G(A) \in P$ and $G(B) \in Q$.
Let ${\rm Ramsey}(P * Q)$ be the set of all graphs which have a ramseian
$P * Q$-partition.

Generalizing a result of Gy\'arf\'as \cite{Gyarfas98}, we prove that if
both $P$ and $Q$ are finitely generated then ${\rm Ramsey}(P * Q)$ is also
finitely generated.
In particular, every class of $(\alpha, \beta)$-polar graphs (which are
generalizations of split graphs) has a finite forbidden induced
subgraph characterization.

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

DIMACS Home Page