Please use this identifier to cite or link to this item: https://gnanaganga.inflibnet.ac.in:8443/jspui/handle/123456789/7631
Title: Ramseian Partitions and Weighted Stability in Graphs
Authors: I. E. Zverovich
I. I. Zverovich
Issue Date: 2005
Publisher: Bulletin of the Institute of Combinatorics and Its Applications
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.
URI: http://gnanaganga.inflibnet.ac.in:8080/jspui/handle/123456789/7631
Appears in Collections:Articles to be qced

Files in This Item:
File SizeFormat 
RAMSEIAN PARTITIONS AND WEIGHTED STABILITY IN GRAPHS.pdf
  Restricted Access
6.79 MBAdobe PDFView/Open Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.