Partitions of Graphs

Mieczysław Borowiecki ()
Additional contact information
Mieczysław Borowiecki: University of Zielona Góra, Faculty of Mathematics, Computer Science and Econometrics

Chapter Chapter 2 in Structural Analysis of Complex Networks, 2011, pp 27-47 from Springer

Abstract: Abstract Many difficult optimization problems on graphs become tractable when restricted to some classes of graphs, usually to hereditary classes. A large part of these problems can be expressed in the vertex partitioning formalism, i.e., by partitioning of the vertex set of a given graph into subsets $${V }_{1},\ldots,\!{V }_{k}$$ called colour classes, satisfying certain constraints either internally or externally, or both internally and externally. These requirements may be conveniently captured by the symmetric k-by-k matrix M. Concepts which are modeled by M-partitions fall naturally into the three types; each is represented in this work by some problem. Any minimal reducible bound for a hereditary property is in some sense the best possible partition. A number of such partitions are given. Clustering is a central optimization problem (among many others) with applications in various disciplines, e.g., computational biology, communications networks, image processing, pattern analysis [41, 53, 60, 57], and numerous other fields. Some new results on k-clustering of graphs are proved. Another type of M-partition is a matching cutset. The main known results on this subject are collected. The last part of this work is devoted to acyclic partitions of graphs where we consider important classes of graphs and their acyclic reducible bounds. For each partition type the complexity of considered problems is given. Also a number of open problems are presented.

Keywords: Colourings; Partitions; Hereditary properties; k-clustering; Domination; Cut matching; Complexity (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-8176-4789-6_2

Ordering information: This item can be ordered from
http://www.springer.com/9780817647896

DOI: 10.1007/978-0-8176-4789-6_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().