Divisibility in additive hereditary graph properties and uniquely partitionable graphs

Rok, strany: 1999, 79 - 87

Let $mcp₁,mcp₂,…,mcp_n$ be graph properties and let $G$ be a graph. A vertex $(mcp₁,mcp₂,…,mcp_n)$-partition of $G$ is a partition V of $V(G)$ such that the induced subgraph $G[V_i]$ has the property $mcp_i$ for each $i=1,2,…,n$. The property $R = mcircPn$ is defined as the set of all graphs having a vertex $(mcp₁,mcp₂,…,mcp_n)$-partition. A graph $G in mcircPn$ is said to be uniquely $(mcircPn)$-partitionable if $G$ has exactly one vertex $(P₁,P₂,…, P_n)$-partition. In this paper we prove for additive hereditary properties $mcp₁,mcp₂,…,mcp_n$ that a uniquely $(mcircPn)$-partitionable graph exists if and only if every pair of these properties are coprime.

ISO 690:

Broere, I., Bucko, J. 1999. Divisibility in additive hereditary graph properties and uniquely partitionable graphs. In Tatra Mountains Mathematical Publications, vol. 18, no.4, pp. 79-87. 1210-3195.

APA:

Broere, I., Bucko, J. (1999). Divisibility in additive hereditary graph properties and uniquely partitionable graphs. Tatra Mountains Mathematical Publications, 18(4), 79-87. 1210-3195.