{"docId":502,"paperId":502,"url":"https:\/\/dmtcs.episciences.org\/502","doi":"10.46298\/dmtcs.502","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":92,"name":"Vol. 12 no. 5"}],"section":[{"sid":16,"title":"Graph and Algorithms","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-00990463","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00990463v1","dateSubmitted":"2015-03-26 16:20:57","dateAccepted":"2015-06-09 14:47:38","datePublished":"2010-01-01 08:00:00","titles":{"en":"Convex Partitions of Graphs induced by Paths of Order Three"},"authors":["Centeno, C. C.","Dantas, S.","Dourado, M. C.","Rautenbach, Dieter","Szwarcfiter, Jayme Luiz"],"abstracts":{"0":"Graphs and Algorithms","en":"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."},"keywords":[["graph convexity"],["convex partition"],"[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}