Convex Partitions of Graphs induced by Paths of Order Three
C. C. Centeno, S. Dantas, M. C. Dourado, Dieter Rautenbach, Jayme Luiz Szwarcfiter
Abstract
A set C of vertices of a graph G is
P3-convex if v∈C for every
path uvw in G with
u,w∈C. We prove that it is NP-complete to decide for
a given graph G and a given integer p
whether the vertex set of G can be partitioned into
p non-empty disjoint P3-convex
sets. Furthermore, we study such partitions for a variety of graph
classes.
Full Text: PDF PostScript