A modification of the certificate
An earlier version of the argument attempted to explicitly reduce the input graph to a t‑minor‑critical graph via edge deletion and contraction before building the Kempe foliated complex and the KF system. However, explicitly constructing a t‑minor‑critical graph is itself NP‑complete, and once such a critical graph is obtained, simple structural checks suffice to decide the existence of a K_t minor. We therefore revise our pipeline: instead of explicitly constructing the t‑minor‑critical graph, we start directly from the input graph, lift from a valid (t-1)‑proper colouring to the Kempe foliated complex, and then perform fold‑obstruction analysis and KF‑system operations. This modification removes the NP‑complete preprocessing step and yields a self‑contained argument.
Authors
- 赵九思
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-11
- DOI
- https://doi.org/10.5281/zenodo.24132058
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint