\(K_{5}\)-free bound for the class of planar graphs (Q852707)

The author defines a \(k\)-diverse colouring of a graph \(G\) to be a proper vertex colouring of \(G\) such that each vertex \(x\) is neighbouring to at least \(\min\{k,d(x)\}\) colours. Given \(k\geq 11\) it is proved via induction that every planar graph admits a \(k\)-diverse colouring using at most \(5k+8\) colours. This is used to produce a \(K_5\)-free bound \(H\) for the class of planar graphs (i.e., each planar graph admits a homomorphism to \(H)\).