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