Berge–Füredi conjecture for linear hypergraphs

Let (V,E)(V,E) be a linear, loopless hypergraph: for distinct hyperedges Vi,VjEV_i,V_j\in E, ViVj1|V_i\cap V_j|\leq 1, and every hyperedge has more than one vertex. Let q(V,E)q(V,E) denote its chromatic index, and let [(V,E)]2[(V,E)]_2 be its 2-section, obtained by replacing every hyperedge with a complete graph on its vertices. Write Δ([(V,E)]2)\Delta([(V,E)]_2) for the maximum degree of this graph.

Berge–Füredi conjecture. A linear (loopless) hypergraph (V,E)(V,E) satisfies

q(V,E)Δ([(V,E)]2)+1.q(V,E) \leq \Delta([(V,E)]_2)+1.

This is the hypergraph analogue of Vizing's upper bound for the chromatic index of a graph. The paper presents results suggesting an approach to the conjecture and gives sufficient conditions for it to hold, including conditions involving the Helly property; its general validity remains open.

Sources & referencesView supporting material

Primary source

Thomas Murff and Xerxes D. Arsiwalla, “Upper Bounds on the Chromatic Index of Linear Hypergraphs”, arXiv:2510.07494 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.