Skip to Main content Skip to Navigation
Journal articles

Convex Partitions of Graphs induced by Paths of Order Three

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:37:45 PM
Last modification on : Monday, October 19, 2020 - 2:34:03 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:17:30 PM


Files produced by the author(s)


  • HAL Id : hal-00990463, version 1



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⟩



Record views


Files downloads