Bounds on Odd and Odd-Even Induced Subgraphs

Qiwen Guo, Gregory Gutin, Yiming Hao, Yongtang Shi, Yong Zhang, Yacong Zhou

arXivarxiv/2608.02339Aug 3, 2026math.COscore 0

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,…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.02339
curl -X POST /api/v1/records/arxiv/2608.02339/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.02339/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'