Speaker: Adam Blumental
Title: Decomposing Graphs into Edges and Triangles
Abstract:
Let $\pi_3(G)$ be the minimum of twice the number of $K_2's$ plus three times the number of $K_3's$ over all edge decompositions of a graph $G$ into copies of $K_2$ and $K_3$. Let $\pi_3(n)$ be the maximum of $\pi_3(G)$ over graphs with $n$ vertices. This specific extremal function was studied by Gy\H{o}ri and Tuza, and recently improved by Kr\'al, Lidick\'y, Martins and Pehova. We extend the proof by giving the exact value of $\pi_3(n)$ for large $n$ and classify the extremal examples.
This is a joint work with Bernard Lidick\'y, Oleg Pikhurko, Yanitsa Pehova, Florian Pfender, and Jan Volec.