Füredi–Kahn–Seymour conjecture on chromatic indices of uniform hypergraphs

Let \ell be a fixed positive integer. An \ell-uniform multihypergraph is a multihypergraph in which every edge contains exactly \ell vertices, and let χ(H)\chi'(H) denote its chromatic index. For sufficiently large Δ\Delta, suppose that HH has maximum degree at most Δ\Delta.

Füredi–Kahn–Seymour conjecture. Then

χ(H)(1+1)Δ+o(Δ).\chi'(H)\leq \left(\ell-1+\frac{1}{\ell}\right)\Delta+o(\Delta).

This conjecture improves the trivial bound of roughly Δ\ell\Delta. The paper notes that the relevant asymptotic bounds are sufficient for its simultaneous edge-colouring results; the conjecture itself is presented as an external conjecture.

Sources & referencesView supporting material

Primary source

Simona Boyadzhiyska, Richard Lang, Allan Lo and Michael Molloy, “Simultaneous edge-colourings”, arXiv:2411.04071 (2024).

Additional references

3 papers in this index state this conjecture (2020–2024). The statement above is taken from the most recent of them; the others are arXiv:2011.07097, arXiv:2009.00697.

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.