Metraipolis › archive › dc_bb4e10da89b0

Three-critical hypergraphs of maximum local edge connectivity two — arXiv:2611.07856

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.07856
License (as archived): CC0-1.0
Archived: 2026-11-06T14:52:49.193Z
SHA-256 of the archived text: 57c93ffe556a89ba301bcf08897ebe371f92e08bcae72ce3e5a226a4c2fe48e5
Stable URL of this page: https://metraipolis.com/documento/dc_bb4e10da89b0

How to cite

Three-critical hypergraphs of maximum local edge connectivity two — arXiv:2611.07856 — arXiv (en), https://arxiv.org/abs/2611.07856 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bb4e10da89b0 (Metraipolis archive dc_bb4e10da89b0, sha256 57c93ffe556a89ba301bcf08897ebe371f92e08bcae72ce3e5a226a4c2fe48e5)

BibTeX

@misc{dcbb4e10da89b0,
  title = {Three-critical hypergraphs of maximum local edge connectivity two — arXiv:2611.07856},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07856},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bb4e10da89b0; sha256 57c93ffe556a89ba301bcf08897ebe371f92e08bcae72ce3e5a226a4c2fe48e5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07856. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a hypergraph \(G\), let \(\chi(G)\) denote its chromatic number and \(\lambda(G)\) the maximum, over pairs of distinct vertices, of the minimum size of an edge cut separating the pair. A hypergraph is \(3\)-critical if its chromatic number is three and every proper subhypergraph is two-colorable. In this paper, we give a recursive characterization of the \(3\)-critical hypergraphs with \(\lambda(G)\le2\). We prove that these are precisely the hypergraphs generated from ordinary odd cycles and an explicit family of labeled-tree hypergraphs by admissible Toft splits. This characterization includes a necessary and sufficient condition for a prescribed split to preserve \(\lambda\le2\). The condition involves only cuts in the first factor and the two traces on the split edge. More generally, we establish an exact cut formula for splits at degree-\(k\) vertices of \((k+1)\)-critical hypergraphs, for every \(k\ge2\). We further prove that the smallest member of this critical class outside the family generated by hyperwheels and both forms of the Hajós join has eight vertices and is unique up to isomorphism. Together, these results resolve two issues left open by Schweser, Stiebitz, and Toft in \emph{Journal of Combinatorics} (2022): the characterization of hypergraphs with \(\lambda(G)=2\) and \(\chi(G)=3\), and whether hyperwheels and Hajós joins suffice to generate all \(3\)-critical hypergraphs in this connectivity range.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.07856 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:24:27.845Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).