Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874788 | Journal of Discrete Algorithms | 2014 | 7 Pages |
Abstract
We study the maximum differential coloring problem, where the vertices of an n-vertex graph must be labeled with distinct numbers ranging from 1 to n, so that the minimum absolute difference between two labels of any two adjacent vertices is maximized. As the problem is NP-hard for general graphs [16], we consider planar graphs and subclasses thereof. We prove that the maximum differential coloring problem remains NP-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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
M.A. Bekos, M. Kaufmann, S. Kobourov, S. Veeramoni,