episciences.org_502_1675063938
1675063938
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
2010
Vol. 12 no. 5
Graph and Algorithms
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 NPcomplete to decide for a given graph G and a given integer p whether the vertex set of G can be partitioned into p nonempty disjoint P(3)convex sets. Furthermore, we study such partitions for a variety of graph classes.
01
01
2010
502
https://hal.science/hal00990463v1
10.46298/dmtcs.502
https://dmtcs.episciences.org/502

https://dmtcs.episciences.org/502/pdf

https://dmtcs.episciences.org/502/pdf