Turán number and decomposition number of intersecting odd cycles

Original · EN

An extremal graph for a given graph H is a graph on n vertices with maximum number of edges that does not contain H as a subgraph. Let s,t be integers and let Hₛ,ₜ be a graph consisting of s triangles and t cycles of odd lengths at least 5 which intersect in exactly one common vertex. Erdős et al. (1995) determined the extremal graphs for Hₛ,₀. Recently, Hou et al. (2016) determined the extremal graphs for H₀,ₜ, where the t cycles have the same odd length q with q≥ 5. In this paper, we further determine the extremal graphs for Hₛ,ₜ with s≥ 0 and t≥ 1. 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)=(n,H) for χ(H)3 and all sufficiently large n. Liu and Sousa (2015) verified the conjecture for Hₛ,₀. In this paper, we further verify Pikhurko and Sousa's conjecture for Hₛ,ₜ with s≥ 0 and t≥ 1.