eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2010-01-01
Vol. 12 no. 5
Graph and Algorithms
10.46298/dmtcs.502
502
journal article
Convex Partitions of Graphs induced by Paths of Order Three
C. C. Centeno
S. Dantas
M. C. Dourado
Dieter Rautenbach
Jayme Luiz Szwarcfiter
Graphs and Algorithms
A set C of vertices of a graph G is P(3)-convex if v is an element of C for every path uvw in G with u, w is an element of 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 P(3)-convex sets. Furthermore, we study such partitions for a variety of graph classes.
https://dmtcs.episciences.org/502/pdf
graph convexity
convex partition
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]