Greedy maximum-clique decompositions (Q1340141): Difference between revisions

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

zbMATH Keywords

clique decomposition

0 references

maximum cliques

0 references

reviewed by

Peter Horák

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

On the Decomposition of Graphs

0 references

The Representation of a Graph by Set Intersections

0 references

On a problem of G. O. H. Katona and T. Tarján

0 references

Q5203068

0 references

The greedy clique decomposition of a graph

0 references

Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs

0 references

full work available at URL

https://doi.org/10.1007/bf01212981

0 references

Identifiers

zbMATH Open document ID

0813.05037

0 references

DOI

10.1007/BF01212981

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1340141

@@ Property / reviewed by @@
-Peter Horák
@@ Property / reviewed by: Peter Horák / rank @@
-Normal rank
@@ Property / reviewed by @@
+Peter Horák
@@ Property / reviewed by: Peter Horák / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+On the Decomposition of Graphs
@@ Property / cites work: On the Decomposition of Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The Representation of a Graph by Set Intersections
+Normal rank
@@ Property / cites work @@
+On a problem of G. O. H. Katona and T. Tarján
@@ Property / cites work: On a problem of G. O. H. Katona and T. Tarján / rank @@
+Normal rank
@@ Property / cites work @@
+Q5203068
@@ Property / cites work: Q5203068 / rank @@
+Normal rank
@@ Property / cites work @@
+The greedy clique decomposition of a graph
@@ Property / cites work: The greedy clique decomposition of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/bf01212981
+Normal rank
@@ Property / OpenAlex ID @@
+W2047022952
@@ Property / OpenAlex ID: W2047022952 / rank @@
+Normal rank