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 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