(Institutul de Matematică şi Informatică al Academiei de Ştiinţe a Moldovei, 2018) Buzatu, Radu; Cataranciuc, Sergiu
In this paper we prove that it is NP-complete to decide whet-
her 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 re-
cursive formula that establishes the maximum nontrivial convex
cover number of a tree.
