文档介绍：Discrete Applied Mathematics 156 (2008) 1652–1660
phs are a natural extension of some classes of graphs which include bipartite graphs, split graphs (.,
graphs whose vertex set can be partitioned into a clique and a stable set) and complements of bipartite graphs.
Following [2], a graph G = (V, E) is called polar if its vertex set V can be partitioned into (A, B) (A or B may
possibly be empty) such that A induces a complete multipartite graph (it is a join of stable sets) and B a (disjoint) union
of cliques (., the complement of a join of stable sets).
We shall say that G is (s, k)-polar if there exists a partition (A, B) where A induces a join of at most s stable sets
and B a union of at most k cliques. Thus polar graphs are just the (∞, ∞)-polar graphs. Notice that not every graph is
polar: the graphs N1 and N2 in Fig. 1 are not polar as can be checked, but if any vertex is removed, the remaining graph
is polar. Observe also that the complement G of an (s, k)-polar graph is a (k, s)-polar graph. Notice that (1, 1)-polar
graphs are just split graphs.
∗
Corresponding author.
E-mail address: tinaz.******@ (T. Ekim).
1 The research of Tınaz Ekim was supported by Grant 200021-101455/1 and Grant 200020-113405 of the Swiss National Science Foundation
whose support is greatl