Nontrivial convex p-cover and nontrivial convex p-partition of a graph were de ned in [1]. The problems of determining whether a graph has a nontrivial convex p-cover or a nontrivial convex p-partition are NP-complete for a xed p  2 [1]. Further, there is a speci c interest in studying these problems for some classes of graphs. Particularly, nontrivial convex p-covers of trees are studied in [2] and [3]. Let G be a graph with n vertices and m edges. Theorem 1. It can be decided in time O(n3) whether a tree G, n  6, has a nontrivial convex p-partition for a xed p, 2  p  bn 3 c. Also, a recursive algorithm is proposed to establish if a tree has a nontrivial convex p-cover for a xed p  2 [3]. Obviously, there exist graphs for which there are no nontrivial convex covers or nontrivial convex partitions or both. It is NP-complete to decide whether a graph can be partitioned into nontrivial convex sets [3].Theorem 2. It can be decided in time O(n4m) whether a graph G can be covered by nontrivial convex sets.