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

Xinmin Hou, Yu Qiu, Boyuan Liu

Published 2015-10-03Version 1

Let $\phi(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 $\phi(n, H)$ parts, of which every part either is a single edge or forms a graph isomorphic to $H$. Pikhurko and Sousa conjectured that $\phi(n,H)=\ex(n,H)$ for $\chi(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.