Three-critical hypergraphs of maximum local edge connectivity two
Abstract
For a hypergraph G, let χ(G) denote its chromatic number and λ(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 λ(G)≤2. 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 λ≤2. 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≥2. 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 λ(G)=2 and χ(G)=3, and whether hyperwheels and Hajós joins suffice to generate all 3-critical hypergraphs in this connectivity range.
Related
- Ollivier--Ricci Idleness Functions and Edge-Connectivity of Hypergraphs
- The maximum spectral radius of outerplanar and planar k-uniform hypergraphs
- On maximum likelihood estimation in the β-model for random hypergraphs
- The maximum spectral radius of uniform hypergraphs whose shadow excludes a complete or complete bipartite minor
- Homological critical points for hypergraphs and simplicial complexes
BibTeX
@misc{yue2026threecritical,
title = {{Three-critical hypergraphs of maximum local edge connectivity two}},
author = {Jun Yue},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07856},
eprint = {2611.07856},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07856},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Three-critical hypergraphs of maximum local edge connectivity two
AU - Jun Yue
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07856
UR - https://arxiv.org/abs/2611.07856
AB - For a hypergraph G, let χ(G) denote its chromatic number and λ(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 λ(G)≤2. 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 λ≤2. 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≥2. 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 λ(G)=2 and χ(G)=3, and whether hyperwheels and Hajós joins suffice to generate all 3-critical hypergraphs in this connectivity range.
ER -