Maximum product of clique partition numbers for complementary graphs
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\).
Problem
What is \[ \max\{cp(G) cp(\bar{G})\} \] where \(G\) ranges over all graphs on \(n\) vertices?The best bound known [1] is
\[
\frac{29}{2000} n^4 + O(n^3) \leq \max\{cp(G) cp(\bar{G})\}
\leq \frac{169}{3600}n^4 + O(n^3) . \]
A sum variation of this problem was proposed by Erdős and solved by Pyber [2] where he proved
\(\displaystyle cc(G)+cc(\bar{G}) \le \frac{1}{4}n^2+2\)
However, it appears that no recent progress has been made on the original problem.