Clique factors in powers of graphs

Abstract

The $k$th power of a graph $G$, denoted $G^k$, has the same vertex set as $G$, and two vertices are adjacent in $G^k$ if and only if there exists a path between them in $G$ of length at most $k$. A $K_r$-factor in a graph is a spanning subgraph in which every component is a complete graph of order $r$. It is easy to show that for any connected graph $G$ of order divisible by $r$, $G^{2r-2}$ contains a $K_r$-factor. This is best possible as there exist connected graphs $G$ of order divisible by $r$ such that $G^{2r-3}$ does not contain a $K_r$-factor. We conjecture that for any 2-connected graph $G$ of order divisible by $r$, $G^r$ contains a $K_r$-factor. This was known for $r\le 3$ and we prove it for $r=4$. We prove a stronger statement that the vertex set of any 2-connected graph $G$ of order $4k$ can be partitioned into $k$ parts of size $4$, such that the four vertices in any part are contained in a subtree of $G$ of order at most 5. More generally, we conjecture that for any partition of $n=n_1+n_2+\cdots +n_k$, the vertex set of any 2-connected graph $G$ of order $n$ can be partitioned into $k$ parts $V_1,V_2,\dots ,V_k$, such that $|V_i|=n_i$ and $V_i\subseteq V(T_i)$ for some subtree $T_i$ of $G$ of order at most $n_i+1$, for $1\le i\le k$.

This version has a slightly simplified proof