Back to Search
Start Over
Co-2-plex vertex partitions
- Source :
- Journal of Combinatorial Optimization. 30:729-746
- Publication Year :
- 2013
- Publisher :
- Springer Science and Business Media LLC, 2013.
-
Abstract
- This paper studies co-k-plex vertex partitions and more specifically co-2-plex vertex partitions. Co-$$k$$k-plexes and $$k$$k-plexes were first introduced in 1978 in the context of social network analysis. However, the study of co-k-plex vertex partitions or decomposing a graphs into degree bounded subgraphs can be at least dated back to the work of Lovasz (Studia Sci Math Hung 1:237---238, 1966). In this paper, we derive analogues for well-known results on the chromatic number, and present two algorithms for constructing co-2-plex vertex partitions. The first algorithm minimizes the number of partition classes while the second algorithm minimizes a weighted sum of the partition classes, where the weight of a partition class depends on the level of adjacency among its vertices.
- Subjects :
- Discrete mathematics
Control and Optimization
Quantitative Biology::Molecular Networks
Applied Mathematics
Neighbourhood (graph theory)
Computer Science Applications
Vertex (geometry)
Combinatorics
Computational Theory and Mathematics
Bounded function
Theory of computation
Discrete Mathematics and Combinatorics
Partition (number theory)
Adjacency list
Chromatic scale
Computer Science::Databases
Mathematics
Subjects
Details
- ISSN :
- 15732886 and 13826905
- Volume :
- 30
- Database :
- OpenAIRE
- Journal :
- Journal of Combinatorial Optimization
- Accession number :
- edsair.doi...........336d75914cf27ec18f9b502b591e93e7