Difference of clique partition number to clique covering number
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
The clique partition number, \( cp(G)\), is the least number of cliques that partition the edge set of \( G\). The clique cover number, \( cc(G)\), is the minimum number of cliques which cover all edges of a graph \( G\).
In 1983, Erdös, Faudree and Ordman proposed the following problem.
Problem [1]
Is there a sequence of graphs \(G_n\) such that \[ cp(G_n)-cc(G_n) = n^2/4 + O(n)?\]In 1985, Caccetta, Erdös, Ordman and Pullman [2] found a sequence \(G_n\) such that
\(\displaystyle cp(G_n)-cc(G_n) = n^2/4 -n^{3/2}/2+ n/4+O(1).\)
Bibliography | |
---|---|
1 | P. Erdös, R. Faudree and E. Ordman, Clique partitions and clique coverings, Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), Discrete Math. 72 (1988), 93-101. |
2 |
L. Caccetta, P. Erdös, E. T. Ordman and N. J. Pullman, The difference
between the clique numbers of a graph, Ars Combinatoria 19
(1985) A, 97-106.
|