Clique partitions and clique coverings (Q1124604): Difference between revisions

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