Affordable Access

Publisher Website

A note on maximum differential coloring of planar graphs

Authors
Journal
Journal of Discrete Algorithms
1570-8667
Publisher
Elsevier
Identifiers
DOI: 10.1016/j.jda.2014.06.004
Keywords
  • Antibandwidth
  • Separation Number
  • Graph Labeling
  • Caterpillar Graph
  • Spider Graph

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.