Ratio of clique partition number to clique covering number
- 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 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\). Let \( G_n\) denote a graph on \( n\) vertices.
Problem (proposed by Erdös, Faudree and Ordman)Determine the largest value \( c\) such that
An example was given in  with \( c = 1/64\).
|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.|