Additive hereditary graph property

Материал из WikiGrapp
Перейти к:навигация, поиск

Additive hereditary graph propertyаддитивное наследуемое свойство графа.

An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let {\mathcal P}_{1}, \ldots, {\mathcal P}_{n} be additive hereditary graph properties. A graph \,G has a property ({\mathcal P}_{1} \circ \cdots \circ
{\mathcal P}_{n}) if there is a partition (V_{1}, \ldots, V_{n}) of \,V(G) into ,n sets such that, for all \,i, the induced subgraph \,G[V_{i}] is in {\mathcal P}_{i}. A property {\mathcal P} is reducible if there are properties {\mathcal Q} , {\mathcal R} such that {\mathcal P} = {\mathcal Q} \circ {\mathcal R}; otherwise it is irreducible.