Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Convex Partitions of ...
Article

Convex Partitions of Graphs induced by Paths of Order Three

C. C. Centeno (1), S. Dantas (2), M. C. Dourado (1), Dieter Rautenbach ORCID (3), Jayme Luiz Szwarcfiter (1)
(1) Instituto de Matemática da Universidade Federal do Rio de Janeiro
(2) Instituto de Matematica [Fluminense]
(3) Institut für Optimierung und Operations Research
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2010
Last modified on
March 31, 2025
Volume 12
vol. 12:5
Graph and Algorithms
DOI
10.46298/dmtcs.502
License
https://about.hal.science/hal-authorisation-v1
Indicators
914
Views
1041
Downloads

Convex Partitions of Graphs induced by Paths of Order Three

C. C. Centeno (1), S. Dantas (2), M. C. Dourado (1), Dieter Rautenbach ORCID (3), Jayme Luiz Szwarcfiter (1)
(1) Instituto de Matemática da Universidade Federal do Rio de Janeiro
(2) Instituto de Matematica [Fluminense]
(3) Institut für Optimierung und Operations Research
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • graph convexity
  • convex partition
Cited by

Source: OpenCitations

  • 3-neighbor bootstrap percolation on grids

    Discussiones Mathematicae Graph Theory

    Authors : Jaka Hedžet ORCID, Michael A. Henning ORCID

    Journal reference : Volume 45, 2023, pp. 283

    DOI : 10.7151/dmgt.2531

  • Some complexity results on cycle-convex partitions

    Procedia Computer Science

    Authors : Guilherme C.M. Gomes, Laila M.V. Lopes, Vinicius F. dos Santos

    Journal reference : Volume 273, 2025, pp. 365-372

    DOI : 10.1016/j.procs.2025.10.320

  • A general framework for path convexities

    Journal of Combinatorial Optimization

    Authors : João Vinicius C. Thompson, Loana T. Nogueira ORCID, Fábio Protti ORCID, Raquel S. F. Bravo ORCID, Mitre C. Dourado ORCID, Uéverton S. Souza ORCID

    Journal reference : Volume 43, 2020, pp. 994-1009

    DOI : 10.1007/s10878-020-00618-9

  • Covering graphs with convex sets and partitioning graphs into convex sets

    arXiv (Cornell University)

    Authors : Lucía M. González, Luciano N. Grippo ORCID, Martín D. Safe ORCID, Vinicius F. dos Santos ORCID

    Journal reference : Volume 158, 2020, pp. 105944

    DOI : 10.1016/j.ipl.2020.105944
Preview
Loading PDF preview...