论文标题
无H-FRE图的集合封面
Clique covers of H-free graphs
论文作者
论文摘要
需要$ n^2/4 $集团来覆盖完整的两部分图的所有边缘$ k_ {n/2，n/2} $，但是如果$ g $没有$ k_ {t，t，t，t，t，t，t，t，t，t，t，t，t，t，n/2} $，则需要多少个集团来覆盖图$ g $的所有边缘？我们证明$ o（| g |^{2-1/（2t）}）$ cliques就足够了；还证明，即使对于没有四个尺寸的稳定组的图形，我们也可能需要线性的许多集团。这解决了在里昂最近的一次会议上讨论的两个问题。
It takes $n^2/4$ cliques to cover all the edges of a complete bipartite graph $K_{n/2,n/2}$, but how many cliques does it take to cover all the edges of a graph $G$ if $G$ has no $K_{t,t}$ induced subgraph? We prove that $O(|G|^{2-1/(2t)})$ cliques suffice; 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.
