Decomposition of Graphs into $(k,r)$-Fans and Single Edges

Let $\varphi (n,H)$ be the largest integer such that, for all graphs $G$ on $n$ vertices, the edge set $E(G)$ can be partitioned into at most $\varphi (n,H)$ parts, of which every part either is a single edge or forms a graph isomorphic to $H$. Pikhurko and Sousa conjectured that $\varphi (n,H)=\text{ex}(n,H)$ for $\chi (H)\text{geqs}3$ and all sufficiently large $n$, where $\text{ex}(n,H)$ denotes the maximum number of edges of graphs on $n$ vertices that does not contain $H$ as a subgraph. A $(k,r)$-fan is a graph on $(r-1)k+1$ vertices consisting of $k$ cliques of order $r$ which intersect in exactly one common vertex. In this paper, we verify Pikhurko and Sousa’s conjecture for $(k,r)$-fans. The result also generalizes a result of Liu and Sousa.