Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs
type: Item
instance of: scholarly article
title: Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs
zbMATH Open document ID: 0813.05036
DOI: 10.1007/BF01212980
author: Sean McGuinness
published in: Combinatorica
publication date: 1995-05-18T00:00:00Z
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).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 700954
zbMATH Keywords: greedy clique decompositions
zbMATH Keywords: maximal cliques
zbMATH Keywords: clique decomposition
zbMATH Keywords: Turán graph
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: On the Decomposition of Graphs
cites work: The Representation of a Graph by Set Intersections
cites work: On a problem of G. O. H. Katona and T. Tarján
cites work: Q5203068
cites work: The greedy clique decomposition of a graph
full work available at URL: https://doi.org/10.1007/bf01212980
OpenAlex ID: W2086045849
description: scientific article; zbMATH DE number 700954