کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653562 | 1632780 | 2014 | 12 صفحه PDF | دانلود رایگان |
The class of split graphs consists of those graphs GG, for which there exist partitions (V1,V2)(V1,V2) of their vertex sets V(G)V(G) such that G[V1]G[V1] is an edgeless graph and G[V2]G[V2] is a complete graph. The classes of edgeless and complete graphs are members of a family L≤∗, which consists of all graph classes that are induced hereditary and closed under substitution. Graph classes considered in this paper are alike to split graphs. Namely a graph class PP is an object of our interest if there exist two graph classes P1,P2∈L≤∗ (not necessarily different) such that for each G∈PG∈P we can find a partition (V1,V2)(V1,V2) of V(G)V(G) satisfying G[V1]∈P1G[V1]∈P1 and G[V2]∈P2G[V2]∈P2. For each such class PP we characterize all forbidden graphs that are strongly decomposable. The finiteness of families of forbidden graphs for PP is analyzed giving a result characterizing classes with a finite number of forbidden graphs.Our investigation confirms, in the class L≤∗, Zverovich’s conjecture describing all induced hereditary graph classes defined by generalized vertex 2-partitions that have finite families of forbidden graphs.
Journal: European Journal of Combinatorics - Volume 39, July 2014, Pages 68–79