Clique partitions and clique coverings
type: Item
instance of: scholarly article
title: Clique partitions and clique coverings
zbMATH Open document ID: 0679.05040
DOI: 10.1016/0012-365X(88)90197-5
author: Edward T. Ordman
author: Ralph Faudree
author: P. Erdős
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: Only undirected graphs without loops or multiple edges are considered here. \(K_n\) is a clique on \(n\) vertices. The clique covering number and the clique partition number of the graph \(G\) is denoted by \(cc(G)\) and \(cp(G)\)respectively. The authors obtain asymptotic results for \(cp(K_n-K_m)\) for m in the range \(\sqrt{n}<m<n\); for example if \(m=cn^a\), \(1/2<a<1\), then \(cp(K_n-K_m)\) is asymptotic to \(c^2n^{2a}\). They apply bounds developed in this connection to bound the maximum value of \(cp(G)/cc(G)\) on graphs G with n vertices, showing it can grow as fast as \(cn^2\) where \(c>1/64\). Further they prove that if \(T_n\) is \(K_n\) minus a matching then, for all \(n\), \((\log n)-1\leq cc(T_n)\leq 2(\log n).\)
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4112628
zbMATH Keywords: clique covering number
zbMATH Keywords: clique partition number
zbMATH Keywords: asymptotic results
zbMATH Keywords: bounds
reviewed by: B. Andrasfai
MaRDI profile type: Publication
cites work: Q3691766
cites work: The Representation of a Graph by Set Intersections
cites work: Clique partitions of the cocktail party graph
cites work: On a clique covering problem of Orlin
cites work: Q4152571
cites work: Q3922720
cites work: Asymptotic values of clique partition numbers
description: scientific article; zbMATH DE number 4112628