Greedy maximum-clique decompositions (Q1340141): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| (One intermediate revision by one other user not shown) | |||
| Property / cites work | |||
| Property / cites work: On the Decomposition of Graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The Representation of a Graph by Set Intersections / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On a problem of G. O. H. Katona and T. Tarján / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5203068 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The greedy clique decomposition of a graph / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/bf01212981 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2047022952 / rank | |||
Normal rank | |||
Latest revision as of 11:05, 30 July 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
