Greedy maximum-clique decompositions (Q1340141): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 03:00, 5 March 2024
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
