Logarithmic improvement conjecture for defective colouring of linear hypergraphs

About 4 years old · traced to

Let r⩾1r\geqslant 1, let Δ\Delta be the maximum degree, and let d⩾2d\geqslant 2. A hypergraph is linear if every two distinct edges intersect in at most one vertex. A dd-defective kk-colouring is a colouring of the vertices with kk colours such that every colour class induces maximum degree at most dd.

Defective-colouring conjecture. Every (r+1)(r+1)-uniform linear hypergraph with maximum degree at most Δ\Delta has a dd-defective colouring with

\nk=O((Δlog⁡Δ⋅log⁡dd)1/r).\nk=\mathcal{O}\left(\left(\frac{\Delta}{\log\Delta}\cdot\frac{\log d}{d}\right)^{1/r}\right).

This would match the lower bound obtained from known examples of linear hypergraphs, up to the implicit constant, and would establish a logarithmic improvement over the general defective-colouring bound for sparse hypergraphs. The conjecture is presented as open in the source.

References

Primary source

António Girão, Freddie Illingworth, Alex Scott and David R. Wood, “Defective Colouring of Hypergraphs”, arXiv:2207.10514 (2022).

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.