On Nontrivial Covers and Partitions of Graphs by Convex Sets

Abstract

In this paper we prove that it is NP-complete to decide whether a graph can be partitioned into nontrivial convex sets. We show that it can be verified in polynomial time whether a graph can be covered by nontrivial convex sets. Also, we propose a recursive formula that establishes the maximum nontrivial convex cover number of a tree.

Keywords

• Convexity
• complexity
• nontrivial convex cover
• nontrivial convex partition
• tree