Greedy maximum-clique decompositions (Q1340141)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Greedy maximum-clique decompositions |
scientific article |
Statements
Greedy maximum-clique decompositions (English)
0 references
18 May 1995
0 references
Consider a clique decomposition of a graph on \(n\) vertices obtained by removing maximum cliques one by one. The author proves that then the sum of the number of vertices in all the cliques in this decomposition is at most \(n^ 2/2\).
0 references
clique decomposition
0 references
maximum cliques
0 references
