Разбиения вершин графов и кораскраски

Abstract

Let P and Q be hereditary classes of graphs. Denote by S(P,Q) the class of all graphs G such that there exists a partition VG=XuY satisfying the following conditions: G(X)ε P and G(Y)εQ. A class P is called U-closed if GuH in P for every graphs G, HεP . Theorem I. If P is a u-closed hereditary class, which has no finite forbidden induced subgraph characterization, and the independence number α(G) is bounded above for all graphs GεQ, then S(P,Q) has no finite forbidden induced subgraph characterization. We also consider co-colorings of graphs.