Color-blind Graphs and Suboptimal Colorings

We consider an arbitrary graph G = (V, E) and let χ(G) be its chromatic number. We show that in any (χ(G) + p)-coloring of the nodes of G (0 ⩽ p ⩽ χ(G)) there exists some node v for which χ(G) different colors occur on nodes located at distance at most ⌈ p 2 ⌉ + 1 from v. We define the notion of color-blind graphs and show that the smallest color-blind graph has at least 30 vertices.