Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 10 min ago
PreprintCC BY 4.0arXiv

Degreewise Cut-Semigroup Saturation for K5-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture

  • SeungJu Lee
Open at sourcePDFDOICite

Abstract

For every positive integer k, we prove that the homogeneous cut semigroup of every K5-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 K5-minor-free cut polytopes with Seymour's planar edge-colouring conjecture. In particular, the known cases k≤ 8 give saturation through height eight.

Related

  1. The List Total Colouring Conjecture is False
    Jonathan A. Noel
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  2. The Partial List Colouring Conjecture is False
    Jonathan A. Noel
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs
    Sylwia Antoniuk, Andrzej Dudek, Andrzej Ruciński
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  4. Locating a Seymour vertex in oriented graphs having minimum outdegree at most 7
    Arpan Sadhukhan, Sagnik Sen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. The forced colouring function of a graph
    G. E. Farr
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lee2026degreewise,
  title = {{Degreewise Cut-Semigroup Saturation for $K_5$-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture}},
  author = {SeungJu Lee},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.12732},
  eprint = {2609.12732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.12732},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Degreewise Cut-Semigroup Saturation for K_5-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
AU  - SeungJu Lee
PY  - 2026
DA  - 2026/09/11
PB  - arXiv
DO  - 10.48550/arxiv.2609.12732
UR  - https://arxiv.org/abs/2609.12732
AB  - 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 edge-colouring conjecture. In particular, the known cases k≤ 8 give saturation through height eight.
ER  -