Restricted greedy clique decompositions and greedy clique decompositions of K_ 4-free graphs

DOI10.1007/BF01212980MaRDI QIDQ1340140zbMATH 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/bf01212980

zbMATH Keywords

clique decompositiongreedy clique decompositionsmaximal cliquesTurán graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

Let \(p\geq 3\). Consider a clique decomposition of a graph on \(n\) vertices obtained by removing first maximal cliques of order at least \(p\) one by one until none remain, then the other edges are removed one by one. The paper shows that the number of cliques in such a decomposition is at most the number of edges in the Turán graph of order \(n\) with no complete subgraph of order \(p\). (By clique decomposition of a graph a partition of its edge set into cliques is meant).

Recommendations

• Greedy clique decompositions and the Turán numbers
• scientific article; zbMATH DE number 1792630
• Greedy maximum-clique decompositions

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
• The greedy clique decomposition of a graph
• The Representation of a Graph by Set Intersections

Cited in

(4)

• Greedy maximum-clique decompositions
• Greedy clique decompositions and the Turán numbers
• Convex hull of face vectors of colored complexes
• Joints in graphs

This page was built for publication: Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs

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