{"id":"arxiv/2608.02339","url":"https://arxiv.org/abs/2608.02339","tags":["math.CO","cs.DM"],"score":0,"title":"Bounds on Odd and Odd-Even Induced Subgraphs","domain":"math.CO","source":"arxiv","authors":["Qiwen Guo","Gregory Gutin","Yiming Hao","Yongtang Shi","Yong Zhang","Yacong Zhou"],"reviews":0,"subject":"math.CO","summary":"Let $G$ be an $n$-vertex graph and let $\\ell:V(G)\\to\\mathbb{F}_2$ prescribe degree parities. A set $S\\subseteq V(G)$ is $\\ell$-admissible if every $v\\in S$ has degree congruent to $\\ell(v)$ modulo $2$ in $G[S]$. Let $h_\\ell(G)$ be the maximum order of an $\\ell$-admissible set, set $f_{\\mathrm{oe}}(G):=\\min_\\ell h_\\ell(G)$, and write $f_o(G):=h_{\\mathbf{1}}(G)$, where $\\mathbf{1}(v)=1$ for every $v\\in V(G).$ We prove three main results for graphs without isolated vertices. First, by extending Zeng's odd-cut method to arbitrary parity prescriptions an introducing a one-sided completion lemma,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-03","reactions":{}}