{"id":"arxiv/2606.29743","url":"https://arxiv.org/abs/2606.29743","tags":["cs.DM","math.CO"],"score":0,"title":"3-packings in Triangulations: Algorithms, bounds, and Complexity","domain":"cs.DM","source":"arxiv","authors":["Prosenjit Bose","Anil Maheshwari","Bobby Miraftab","Yota Otachi"],"reviews":0,"subject":"cs.DM","summary":"We study $H$-packings in plane triangulations for the three-vertex graphs $H\\in\\{P_3,K_3,P_2\\cup P_1\\}$. For a graph $H$, let $λ_H(G)$ denote the maximum size of an $H$-packing in $G$, with the convention that for $H=P_2\\cup P_1$ the copies are required to be induced. For $P_3$-packings, we prove that every triangulation $G$ on $n$ vertices satisfies $λ_{P_3}(G)\\ge \\left\\lfloor \\frac n5\\right\\rfloor$, and show that this lower bound is asymptotically tight. We also study triangle packings in triangulations and provide lower bounds for $λ_{K_3}(G)$ in terms of the maximum degree and the degree…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-29","reactions":{}}