Covering by \(4\)-cycles

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}\).

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.