On Maximum Differential Coloring of Planar Graphs

arXiv1302.7085MaRDI QIDQ6239969FDOQ6239969

Sankar Veeramoni, Markus Geyer, Stephen G. Kobourov, Aparna Das, Michael A. Bekos, Michael A. Kaufmann

Publication date: 28 February 2013

Abstract: We study the emph{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 NPH for general graphs~cite{leung1984}, we consider planar graphs and subclasses thereof. We initially prove that the maximum differential coloring problem remains NPH, even for planar graphs. Then, we present tight bounds for regular caterpillars and spider graphs. Using these new bounds, we prove that the Miller-Pritikin labeling scheme~cite{miller89} for forests is optimal for regular caterpillars and for spider graphs. Finally, we describe close-to-optimal differential coloring algorithms for general caterpillars and biconnected triangle-free outer-planar graphs.

This page was built for publication: On Maximum Differential Coloring of Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239969)