# Conjecture (proposed by Erdös and Faudree[1])

Suppose a graph $$G$$ has $$4n$$ vertices with minimum degree at least $$2n$$. Then $$G$$ contains $$n$$ vertex-disjoint copies of $$C_4$$.

Alon and Yuster [1] proved that for any fixed bipartite graph $$H$$ on $$h$$ vertices, any graph $$G$$ with $$n$$ vertices, where $$h$$ divides $$n$$, can be covered by vertex-disjoint copies of $$H$$ if the minimum degree of $$G$$ is at least $$(1/2+\epsilon)n$$ for $$n$$ sufficiently large.

In 1982, Erdös, Goodman and Pósa [2] proved that the minimum number of cliques which cover all edges of a graph $$G$$, denoted by $$cc(G)$$, equals the minimum cardinality of a set $$S$$ such that $$G$$ is the intersection graph of some family of subsets of $$S$$. A natural lower bound for $$cc(G)$$ is the maximum number $$h(G)$$ of edges no two of which are covered by the same clique.

Parthasaraty and Choudum [3] conjectured that $$\chi(\bar{G}) \leq h(G)$$ where $$\bar{G}$$ denotes the complement of $$G$$. This was investigated by Erdös [4] who showed, in fact, that almost all graphs satisfy $$\chi(\bar{G}) \geq h(G)$$. Furthermore, for sufficiently large $$t$$ and $$n$$, there exists a graph $$G$$ on $$n$$ vertices without isolated vertices satisfying $$h(G) \leq t$$ and $$\chi(\bar{G}) \geq n^c$$, where $$c$$ is a constant depending only on $$t$$ (and independent of $$n$$).

Brigham and Dutton [5] proved that any graph without isolated vertices with $$h(G) \leq 2$$ satisfies $$\chi(\bar{G}) \leq h(G)$$ and this was later improved to graphs with $$h(G) \leq 5$$.

Kostochka [6] proved that there exists a graph $$G$$ on $$n$$ vertices without isolated vertices satisfying $$h(G)=6$$ and $$\chi(\bar{G}) \geq n^{1/15}$$.

Bibliography
1 N. Alon and R. Yuster, $$H$$-factors in dense graphs, J. Comb. Theory Ser. B 66 (1996), 269-282.
2 P. Erdös, A. W. Goodman and L. Pósa, The representation of a graph by set intersections, Canad. J. Math. 18 (1966), 106-112.
3 K. R. Parthasaraty and S. A. Choudum, The edges clique cover number of products of graphs, J. Math. Phys. Sci. 10 (1976), 255-261.
4 P. Erdös, On the covering of the vertices of a graph by cliques, J. Math. Res. Exposition 2 (1982) no. 1, 93-96.
5 R. C. Brigham and R. D. Dutton, On clique covers and independence numbers of graphs, Discrete Math. 44 (1983), 139-144.
6