2015/10/03 by Xinmin Hou, Yu Qiu, Hou, Xinmin +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1510.00811
openalex publication_date 2015/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let ϕ(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 ϕ(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.