← All problems

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

6 years old · traced to

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.

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.

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

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.