Vertex covers by edge disjoint cliques (Q5955194)

Let \(f(n,t,k)\) be the largest minimum degree of a graph on \(n\) vertices which has no system of \(K_t\)-subgraphs covering every vertex at least once but at most \(k\) times. It is shown that if \(t\geq 3\), \(k\geq 2\), \(n\geq 6t^2-4t\), \(n=q\bigl[(t-1)k+1\bigr]+r\) (here \(1\leq r\leq (t-1)k+1\)), then \(f(n,t,k)\) is either \(n-qk-\lceil {r \over t-1}\rceil\) or one bigger. Also, for \(n\geq 6\), \(k\geq (n-1)/2\), \(f(n,3,k)=\lceil {n\over 2}\rceil\) holds. If \(H\) is a graph with \(\chi(H)\geq 4\), and there is a vertex \(u\) such that \(\chi(H-\{u\})<\chi(H)\) and if \(G\) is a graph on \(n\geq n_0(\varepsilon)\) vertices with minimum degree at least \((1-{1\over {\chi(H)-1}}+\varepsilon)n\) then \(G\) can be vertex covered with edge disjoint copies of \(H\). The threshold function for the existence of a vertex cover with edge disjoint \(K_t\)'s with every vertex covered at most twice is calculated. This two hitting times (minimal number of edges for it, and that every vertex be in some \(K_t\)) are shown to be almost surely equal.