Complete partitions of graphs (Q949754)

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.