K 5 -free bound for the class of planar graphs
Reza Naserasr · 2006
We define k-diverse colouring of a graph to be a proper vertex colouring in which every vertex x, sees min{k, d(x)} different colours in its neighbors. We show that for given k there is an f(k) for which every planar graph admits a k-diverse colouring using at most f(k) colours. Then using this colouring we obtain a K5-free graph H for which every planar graph admits a homomorphism to it, thus another proof for the result of J. Neˇsetˇril, P. Ossona de Mendez. 1