Edge-colouring conjecture for d-interval hypergraphs

Let HH be a hypergraph of dd-intervals. Let χe(H)\chi_e(H) denote its edge chromatic number, and let Δ\Delta be the maximum degree of a point on any line. Edge-colouring conjecture. Then

χe(H)dΔ.\chi_e(H) \le d\Delta.

For d=2d=2, this strengthens the previously raised conjecture that the edge chromatic number is at most twice the maximum size of an intersecting subhypergraph. The bound is presented as a conjectural consequence suggested by the weighted fractional-covering framework and remains open.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Tomas Kaiser and Shira Zerbib, “Fractional covers and matchings in families of weighted d-intervals”, arXiv:1402.2064 (2014).

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.