The Lean Number of a Hypergraph

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 $k$-uniform, $k$-partite, wide-path connected, or $r$-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 $130$ knots and links.