On Maximum Differential Graph Coloring

Hu, Yifan and Kobourov, Stephen G. and Veeramoni, Sankar (2011) On Maximum Differential Graph Coloring. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010 , pp. 274-286(Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_25).

Full text not available from this repository.


We study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_25
Classifications: P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1213

Actions (login required)

View Item View Item