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

Abstract

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 $ϕ(n,H)=\ex(n,H)$ for $χ(H)\geqs3$ and all sufficiently large $n$, where $\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.

arXiv comment18 pages