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, Konstanz, Germany , pp. 274-286 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_25).

Full text not available from this repository.

Abstract

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
ID Code:1213

Repository Staff Only: item control page

References

Blache, G., Karpinski, M., Wirtgen, J.: On approximation intractability of the bandwidth problem. Technical Report TR98-014, University of Bonn (1998)

Brewer, C.: ColorBrewer - Color Advice for Maps, http://www.colorbrewer.org

Calamoneri, T., Massini, A., Török, L., Vrt’o, I.: Antibandwidth of complete k-ary trees. Electronic Notes in Discrete Mathematics 24, 259–266 (2006)

Dillencourt, M.B., Eppstein, D., Goodrich, M.T.: Choosing colors for geometric graphs via color space embeddings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 294–305. Springer, Heidelberg (2007)

Dobrev, S., Královic, R., Pardubská, D., Török, L., Vrt’o, I.: Antibandwidth and cyclic antibandwidth of hamming graphs. Electronic Notes in Discrete Mathematics 34, 295–300 (2009)

Gansner, E.R., Hu, Y.F., Kobourov, S.G.: GMap: Visualizing graphs and clusters as maps. In: IEEE Pacific Visualization Symposium (PacVis), pp. 201–208 (2010)

Gansner, E.R., Hu, Y.F., Kobourov, S.G., Volinsky, C.: Putting recommendations on the map: visualizing clusters and relations. In: 3rd ACM Conference on Recommender Systems (RecSys), pp. 345–348 (2009)

Hu, Y.F., Scott, J.A.: A multilevel algorithm for wavefront reduction. SIAM Journal on Scientific Computing 23, 1352–1375 (2001)

Kumfert, G., Pothen, A.: Two improved algorithms for envelope and wavefront reduction. BIT 35, 1–32 (1997)

Leung, J., Vornberger, O., Witthoff, J.: On some variants of the bandwidth minimization problem. SIAM Journal on Computing 13, 650 (1984)

Papadimitriou, C.: The NP-Completeness of the bandwidth minimization problem. Computing 16, 263–270 (1975)

Raspaud, A., Schröder, H., Sýkora, O., Török, L., Vrt’o, I.: Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discrete Mathematics 309(11), 3541–3552 (2009)

Sloan, S.W.: An algorithm for profile and wavefront reduction of sparse matrices. International Journal for Numerical Methods in Engineering 23, 239–251 (1986)

Török, L., Vrt’o, I.: Antibandwidth of three-dimensional meshes. Discrete Mathematics 310(3), 505–510 (2010)

Unger, W.: The complexity of the approximation of the bandwidth problem. In: Proceedings of the 39th Symposium on Foundations of Computer Science (FOCS), pp. 82–91 (1998)

Wang, X., Wu, X., Dumitrescu, S.: On explicit formulas for bandwidth and antibandwidth of hypercubes. Discrete Applied Mathematics 157(8), 1947–1952 (2009)

Wong, W.W., Wong, C.K.: Minimum K-Hamiltonian graphs. Journal of Graph Theory 8, 155–165 (2006)