Complete partitions of graphs (Q949754)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complete partitions of graphs |
scientific article |
Statements
Complete partitions of graphs (English)
0 references
21 October 2008
0 references
Complete partitions of a graph are vertex partitions such that any two classes are related by an arc. The authors compute tight lower and upper bounds for the maximum number of classes in a complete partition. A technique used is that of finding the largest integer \(\beta(G)\) such that there exists a subgraph \(H\subseteq G\) with maximum degree at most \(t\) and at least \(t^2/2\) edges. The results may be used in many other contexts such as colouring and determining chromatic numbers.
0 references
complete partitions
0 references
vertex partitions
0 references
complexity
0 references
0 references