C4-Saturation Obstruction for Comb-Cores: A Certificate-Based Approach to Edge-Completion
We prove that a specific comb-core graph H on 7 vertices, while avoiding all power-of-twocycle lengths, becomes C4-saturated relative to its degree-deficit vertices. This saturationproperty implies that every edge-completion of H achieving minimum degree δ ≥ 3 mustcontain a 4-cycle. We provide explicit 3-path witnesses as checkable certificates for thesaturation claim.
Authors
- Jonas Jakob Gebendorfer
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-01-30
- DOI
- https://doi.org/10.5281/zenodo.18433367
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- article
- Field-Weighted Citation Impact
- 0.00