A note on maximum differential coloring of planar graphs

We study the maximum differential coloring problem, where the vertices of an n-vertex graph must be labeled with distinct numbers ranging from 1to n, so that the minimum absolute difference between two labels of any two adjacent vertices is maximized. As the problem isNP-hard forgeneral graphs[16], we consider planar graphs and subclasses thereof. We prove that the maximum differential coloring problem remainsNP-hard, even for planar graphs. We also present tight bounds for regular caterpillars and spider graphs. Using these new bounds, we prove that the Miller-Pritikin labeling scheme[19]for forests is optimal for regular caterpillars and for spider graphs.