Logarithmic improvement conjecture for defective colouring of linear hypergraphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.