Bounds on Odd and Odd-Even Induced Subgraphs
Abstract
Let G be an n-vertex graph and let ℓ:V(G)→𝔽2 prescribe degree parities. A set S⊆ V(G) is ℓ-admissible if every v∈ S has degree congruent to ℓ(v) modulo $2$ in G[S]. Let hℓ(G) be the maximum order of an ℓ-admissible set, set foe(G):=minℓ hℓ(G), and write fo(G):=h1(G), where 1(v)=1 for every v∈ V(G). We prove three main results for graphs without isolated vertices. First, by extending Zeng's odd-cut method to arbitrary parity prescriptions and introducing a one-sided completion lemma, we show that hℓ(G)≥ 2n/11 for every ℓ. Consequently, foe(G)≥ 2n/11, improving the previous bound 2n/21. Second, for bipartite graphs we derive lower bounds on fo(G) in terms of the 𝔽2-rank of the bipartite adjacency matrix and combine them to obtain fo(G)≥ (1/4+1/256)n=65/256n. Thus, in the bipartite case, the factor $2$ in Scott's bound fo(G)≥ n/(2χ(G)) can be replaced by 128/65<2. Finally, a fourth-moment argument gives, for α=α(G)≥2 and δ(G)≥ 1, fo(G)≥ α/2+log3α/8 −1/4log3log3√α. We also construct bipartite graphs satisfying fo(G)≤ α(G)/2+log2 (α(G)+1)+1/2, showing that the logarithmic additive improvement over Scott's bound fo(G)≥α(G)/2 has the optimal order of magnitude.
Related
- Extremal even-cycle-free subgraphs of the k-ary n-cube
- Sharp bounds for Duke--Erdős--Rödl problems on cycle-connected subgraphs
- Large induced subgraphs with k vertices of maximum degree
- A proof of Vince's conjecture on the average order of connected induced subgraphs
- A Note on Vertex-Critical Induced Subgraphs of Shift Graphs
BibTeX
@misc{guo2026bounds,
title = {{Bounds on Odd and Odd-Even Induced Subgraphs}},
author = {Qiwen Guo and Gregory Gutin and Yiming Hao and Yongtang Shi and Yong Zhang and Yacong Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.02339},
eprint = {2608.02339},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.02339},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bounds on Odd and Odd-Even Induced Subgraphs
AU - Qiwen Guo
AU - Gregory Gutin
AU - Yiming Hao
AU - Yongtang Shi
AU - Yong Zhang
AU - Yacong Zhou
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2608.02339
UR - https://arxiv.org/abs/2608.02339
AB - Let G be an n-vertex graph and let ℓ:V(G)→𝔽_2 prescribe degree parities. A set S⊆ V(G) is ℓ-admissible if every v∈ S has degree congruent to ℓ(v) modulo $2$ in G[S]. Let h_ℓ(G) be the maximum order of an ℓ-admissible set, set f_oe(G):=min_ℓ h_ℓ(G), and write f_o(G):=h_1(G), where 1(v)=1 for every v∈ V(G). We prove three main results for graphs without isolated vertices. First, by extending Zeng's odd-cut method to arbitrary parity prescriptions and introducing a one-sided completion lemma, we show that h_ℓ(G)≥ 2n/11 for every ℓ. Consequently, f_oe(G)≥ 2n/11, improving the previous bound 2n/21. Second, for bipartite graphs we derive lower bounds on f_o(G) in terms of the 𝔽_2-rank of the bipartite adjacency matrix and combine them to obtain f_o(G)≥ (1/4+1/256)n=65/256n. Thus, in the bipartite case, the factor $2$ in Scott's bound f_o(G)≥ n/(2χ(G)) can be replaced by 128/65<2. Finally, a fourth-moment argument gives, for α=α(G)≥2 and δ(G)≥ 1, f_o(G)≥ α/2+log_3α/8 −1/4log_3log_3√α. We also construct bipartite graphs satisfying f_o(G)≤ α(G)/2+log_2 (α(G)+1)+1/2, showing that the logarithmic additive improvement over Scott's bound f_o(G)≥α(G)/2 has the optimal order of magnitude.
ER -