# 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.