| Summary: | It takes <i>n</i><sup>2</sup>/4 cliques to cover all the edges of a complete bipartite graph <i>K</i><sub><i>n/2,n/2</i></sub>, but how many cliques does it take to cover all the edges of a graph <i>G</i> if <i>G</i> has no
<i>K</i><sub><i>t,t</i></sub> induced subgraph? We prove that <i>O</i>(<i>n</i><sup><i>2—1/(2t)</i></sup>) cliques suffice for every <i>n</i>-vertex graph; and also prove that, even for graphs with no stable set of size four, we may need more than linearly many cliques. This settles two questions discussed at a recent conference in Lyon.
|
|---|