The Lean Number of a Hypergraph
arXiv:2607.14015
The paper defines a new type of hypergraph coloring called lean coloring, introduces the lean number as a measure of such colorings, and studies its computational complexity and bounds for various classes of hypergraphs, including applications to knots and links.
Abstract
Inspired by the notion of tricolorability of knots, we introduce the concept of lean coloring for hypergraphs and the associated lean number of a hypergraph. Lean coloring often involves very few colors, yet still requires the methods of usual graph coloring, forcing the overall complexity to be NP-Hard. We provide two alternative formulations of the lean coloring problem that involve a type of coloring on abstract simplicial complexes and a partial coloring on bipartite graphs. We then provide bounds for the lean numbers of hypergraphs that are -uniform, -partite, wide-path connected, or -complete. Python-like script is included to allow the implementation and study of a lean coloring algorithm. We conclude with some directions for future work and present the lean numbers of knots and links.
22 pages, 69 figures