Ratio 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\). Let \( G_n\) denote a graph on \( n\) vertices.
Problem (proposed by Erdös, Faudree and Ordman)
Determine the largest value \( c\) such that
\(\displaystyle \frac {cp (G_n)}{cc(G_n)} > c n^2 \)
for infinitely many values of \( n\).
An example was given in [1] with \( c = 1/64\).
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. |