Cubic removal for chain graphs and a sharp regular-layer bound
For every bipartite graph on a fixed partition of sizes m and n, we prove a deterministic cubic removal bound D <= C_*(mnI)^(1/3), where D is the edit distance to chain graphs, I counts induced copies of 2K2, and C_* is approximately 8.4407085. The normalized exponent 1/3 is optimal. We also prove a degree-variance bound, show that sqrt(8) is the sharp asymptotic constant for equal row degrees, and give the lower bound 4^(1/3) for the best cubic constant.
Authors
- Zihuan Xu
Institutions
- Capital Normal University (CN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-24
- DOI
- https://doi.org/10.5281/zenodo.23611730
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint