Upper Bounds on the Chromatic Index of Linear Hypergraphs

Abstract

We address the problem of finding upper bounds on the chromatic index $q(V,E)$ of linear (and loopless) hypergraphs. The first bound we find is defined through a color-preserving group on a proper and minimally edge-colored linear hypergraph, whose orbits serve as a finer partition to the hypergraph's coloring, thereby yielding an upper bound on $q(V,E)$. The next set of theorems in this paper relates to combinatorial properties of hypergraph coloring. Our results suggest a plausible approach to solving the Berge-Füredi conjecture, providing an upper bound on the chromatic index that directly relates $q(V,E)$ and $\hat{I}”([(V,E){]}_2)+1$. Furthermore, we provide three sufficient conditions for the conjecture to hold within this framework, when involving the Helly property for hypergraphs.

20 pages, 10 figures