Logarithmic improvement conjecture for defective colouring of linear hypergraphs
Let , let be the maximum degree, and let . A hypergraph is linear if every two distinct edges intersect in at most one vertex. A -defective -colouring is a colouring of the vertices with colours such that every colour class induces maximum degree at most .
Defective-colouring conjecture. Every -uniform linear hypergraph with maximum degree at most has a -defective colouring with
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
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.