Logarithmic improvement conjecture for defective colouring of linear hypergraphs

Let r1r\geqslant 1, let Δ\Delta be the maximum degree, and let d2d\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Δlogdd)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.

Sources & referencesView supporting material

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.