Abstract
Given an n-vertex graph G and two positive integers d,k ∈ ℕ, the (d,kn)-differential coloring problem asks for a coloring of the vertices of G (if one exists) with distinct numbers from 1 to kn (treated as colors), such that the minimum difference between the two colors of any adjacent vertices is at least d. While it was known that the problem of determining whether a general graph is (2,n)-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit (2,n)-differential colorings. For practical reasons, we also consider color ranges larger than n, i.e., k > 1. We show that it is NP-complete to determine whether a graph admits a (3,2n)-differential coloring. The same negative result holds for the (\(\lfloor2n/3\rfloor,2n\))-differential coloring problem, even in the case where the input graph is planar.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bansal, R., Srivastava, K.: Memetic algorithm for the antibandwidth maximization problem. Journal of Heuristics 17, 39–60 (2011)
Bekos, M., Kaufmann, M., Kobourov, S., Veeramoni, S.: A note on maximum differential coloring of planar graphs. Journal of Discrete Algorithms (2014)
Bekos, M., Kobourov, S., Kaufmann, M., Veeramoni, S.: The maximum k-differential coloring problem. Arxiv report (2014), http://arxiv.org/abs/1409.8133
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)
Duarte, A., Martí, R., Resende, M., Silva, R.: Grasp with path relinking heuristics for the antibandwidth problem. Networks 58(3), 171–189 (2011)
Ellson, J., Gansner, E., Koutsofios, E., North, S., Woodhull, G.: Graphviz and dynagraph static and dynamic graph drawing tools. In: Jünger, M., Mutzel, P. (eds.) Graph Drawing Software, pp. 127–148. Springer, Heidelberg (2004)
Gansner, E., Hu, Y., Kobourov, S.: Gmap: Visualizing graphs and clusters as maps. In: 2010 IEEE Pacific Visualization Symposium (PacificVis), pp. 201–208 (2010)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Hale, W.: Frequency assignment: Theory and applications. Proceedings of the IEEE 68(12), 1497–1514 (1980)
Hu, Y., Kobourov, S., Veeramoni, S.: On maximum differential graph coloring. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 274–286. Springer, Heidelberg (2011)
Isaak, G.: Powers of hamiltonian paths in interval graphs. Journal of Graph Theory 27, 31–38 (1998)
Leung, J.Y.-T., Vornberger, O., Witthoff, J.D.: On some variants of the bandwidth minimization problem. SIAM Journal on Computing 13(3), 650–667 (1984)
Miller, Z., Pritikin, D.: On the separation number of a graph. Networks 19(6), 651–666 (1989)
Papadimitriou, C.: The NP-Completeness of the bandwidth minimization problem. Computing 16, 263–270 (1975)
Proskurowski, A., Syso, M.: Efficient vertex- and edge-coloring of outerplanar graphs. SIAM Journal on Algebraic Discrete Methods 7(1), 131–136 (1986)
Purves, D., Lotto, R.B.: Why we see what we do: An empirical theory of vision. Sinauer Associates (2003)
Raspaud, A., Schröder, H., Sýkora, O., Török, L., Vrt’o, I.: Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discrete Math. 309(11), 3541–3552 (2009)
Wang, X., Wu, X., Dumitrescu, S.: On explicit formulas for bandwidth and antibandwidth of hypercubes. Discrete Applied Mathematics 157(8), 1947–1952 (2009)
Weili, Y., Xiaoxu, L., Ju, Z.: Dual bandwidth of some special trees. Journal of Zhengzhou University (Natural Science) 35(3), 16–19 (2003)
Yixun, L., Jinjiang, Y.: The dual bandwidth problem for graphs. Journal of Zhengzhou University (Natural Science) 35(1), 1–5 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bekos, M.A., Kaufmann, M., Kobourov, S., Veeramoni, S. (2015). The Maximum k-Differential Coloring Problem. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, JJ., Wattenhofer, R. (eds) SOFSEM 2015: Theory and Practice of Computer Science. SOFSEM 2015. Lecture Notes in Computer Science, vol 8939. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46078-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-662-46078-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46077-1
Online ISBN: 978-3-662-46078-8
eBook Packages: Computer ScienceComputer Science (R0)