Ramseian Partitions and Weighted Stability in Graphs

Abstract

Let 1' and Q be hereditary classes of graphs. A class of graphs C is called a-bounded (respectively, w-bounded) if there exists a constant C such that a(G) ~ C (respectively, w(G) ~ C) for each graph GE C. Here a(G) and w(G) are the stability number and the clique number of G, respectively. The ordered pair (P, Q) is called Ramseian if both P and Qare polynomially recognizable, P is a-bounded, and Q is w-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 AU B = V(G) with G(A) E 'P and G(B) E Q, where G(X) denotes the subgraph of G induced by a set X <;; V(G). A class of graphs C is called a,,, -polynomial if there exists a polynomialtime algorithm to calcule the weighted stability number a,,,(G) for all graphs G E C. A class of graphs C is called a,,, -complete if the corresponding decision problem is NP-complete for graphs in C. Our main results are the following theorems.