A p-centered coloring for the grid using O(p) colors

07/23/2022

∙

by   Mathew Francis, et al.

∙

0

∙

share

A p-centered coloring of a graph G, where p is a positive integer, is a coloring of the vertices of G in such a way that every connected subgraph of G either contains a vertex with a unique color or contains more than p different colors. We give an explicit construction of a p-centered coloring using O(p) colors for the planar grid.