1UFRJ - Instituto de Matemática (Instituto de Matemática, Universidade Federal do Rio de Janeiro, P.O. Box 68530, CEP 21945-970, Rio de Janeiro, RJ, Brasil. - Brésil)
Abstract : 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://hal.inria.fr/hal-00990463
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s
<>
Soumis le : mardi 13 mai 2014 - 15:37:45
Dernière modification le : mercredi 29 novembre 2017 - 10:26:21
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:17:30
C. C. Centeno, S. Dantas, M. C. Dourado, Dieter Rautenbach, Jayme Luiz Szwarcfiter. Convex Partitions of Graphs induced by Paths of Order Three. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (5), pp.175-184. 〈hal-00990463〉
