Degreewise Cut-Semigroup Saturation for $K_5$-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
For every positive integer $k$, we prove that the homogeneous cut semigroup of every $K_5$-minor-free graph is saturated at height $k$ if and only if every planar $k$-graph is $k$-edge-colourable. Here a $k$-graph is a loopless $k$-regular multigraph in which every odd vertex cut has size at least $k$. A triangle expansion of a cubic plane dual converts cut decompositions into perfect-matching decompositions. The converse uses symmetric difference with a fixed perfect matching. The equivalence identifies the normality conjecture for $K_5$-minor-free cut polytopes with Seymour's planar…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.12732
curl -X POST /api/v1/records/arxiv/2609.12732/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.12732/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'