Defective Colouring of Hypergraphs

Abstract

We prove that the vertices of every $(r+1)$-uniform hypergraph with maximum degree $\hat{I}”$ may be coloured with $c(\frac{\hat{I}}{”}d+1{)}^{1/r}$ colours such that each vertex is in at most $d$ monochromatic edges. This result, which is best possible up to the value of the constant $c$, generalises the classical result of Erdős and Lovász who proved the $d=0$ case.

11 pages; revised argument in section 2.2, results unchanged