Greedy maximum-clique decompositions

DOI10.1007/BF01212981MaRDI QIDQ1340141zbMATH OpenOpenAlexFDO

Authors Sean McGuinness

Publication date 18 May 1995

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01212981

zbMATH Keywords

clique decompositionmaximum cliques

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

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\).

Recommendations

• scientific article; zbMATH DE number 1792630
• The greedy clique decomposition of a graph
• Greedy clique decompositions and the Turán numbers

Cites work

• scientific article; zbMATH DE number 4196017 (Why is no real title available?)
• On a problem of G. O. H. Katona and T. Tarján
• On the Decomposition of Graphs
• Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs
• The greedy clique decomposition of a graph
• The Representation of a Graph by Set Intersections

Cited in

(9)

• Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs
• Greedy clique decompositions and the Turán numbers
• An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
• The greedy clique decomposition of a graph
• scientific article; zbMATH DE number 1094321 (Why is no real title available?)
• scientific article; zbMATH DE number 1792630 (Why is no real title available?)
• An algorithm for the decomposition of graphs into cliques
• Decomposing graphs into edges and triangles
• Greedy friendship decompositions of graphs

This page was built for publication: Greedy maximum-clique decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1340141)