## DIMACS TR: 2002-13

## Graph Ramseian bipartitions and weighted stability

### Authors: I. E. Zverovich and I. I. Zverovich

**
ABSTRACT
**

Let *P* and *Q* be hereditary
classes of graphs.
The ordered pair (*P*, *Q*) is called
{\em Ramseian} if both *P* and *Q*
are polynomially recognizible,
*P* is \alpha-bounded, and
*Q* is \omega-bounded.
Let (*P*, *Q*) be an ordered pair of
graph classes.
We denote by *P***Q* the class of all
graphs G such that there exists a partition
A \cup B = V(G) with
- G(A) \in
*P* and
- G(B) \in
*Q*,

where G(X) denotes the subgraph of G induced by a set
X \subseteq V(G).

A class of graphs *C* is called *\alpha_w-polynomial*
if there exists a polynomial-time algorithm for calculation
the weighted stability number \alpha_w(G) for all graphs
G \in *C*.
A class of graphs *C* is called *\alpha_w-complete*
if the corresponding decision problem is NP-complete for
graphs in *C*.

Our main result is the following theorem.
**Theorem***
Let (**P*, *Q*) be a Ramseian pair.

(i) If *Q* is an \alpha_w-polynomial class then
the class *P***Q* is also \alpha_w-polynomial.

(ii) If *Q* is an \alpha_w-complete class then
the class *P***Q* is also \alpha_w-complete.

A similar results for \omega_w-polynomial classes and
\omega_w-complete classes are easily follow (\omega_w(G)
is the weighted clique number of a graph G).
Finally, a recent result of Alekseev and Lozin (2002) is a particular
case of our main theorem.

**Keywords**: Hereditary class, forbidden induced subgraphs,
Ramseian partition, weighted stability number.

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

DIMACS Home Page