{"id":"arxiv/2608.01396","url":"https://arxiv.org/abs/2608.01396","tags":["math.CO"],"score":0,"title":"Three Graffiti.pc Conjectures on Largest Induced Trees: Proofs of Conjectures 141, 142, and 143","domain":"math.CO","source":"arxiv","authors":["Alper Ferudun"],"reviews":0,"subject":"math.CO","summary":"For a finite simple graph $G$, let $t(G)$ be the largest order of an induced tree and let $g(G)$ be the girth. We prove three consecutive conjectures of DeLaViña's Graffiti.pc program. First, writing $\\ell(v)$ for the independence number of the subgraph induced by the neighbourhood of $v$, we prove $t(G) \\ge \\lfloor g(G)/2 \\rfloor - 1 + \\max_{v \\in V(G)} \\ell(v)$. Second, if $\\mathrm{Per}(G)$ is the periphery and $f(G) = \\max_x d(x, \\mathrm{Per}(G))$, we prove $t(G) \\ge \\frac{2}{3} g(G) + f(G)$, and establish the stronger integral bound $t(G) \\ge f(G) + \\lceil 2g(G)/3 \\rceil$ when $G$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-02","reactions":{}}