×

Vertex coloring of a graph for memory constrained scenarios. (English) Zbl 1455.68148

A (proper) \(k\)-vertex coloring of an undirected graph \(G=(V, E)\) with colors \(C = \{c_1, \dots, c_k\}\) is a function \(\phi : V \to C\) for which \(\phi(a) \neq \phi(b)\) whenever \(\{a,b\} \in E\). A graph \(G\) is \(k\)-colorable when it admits a \(k\)-vertex coloring. The chromatic number of \(G\) is the smallest \(k\) for which \(G\) is \(k\)-colorable. When \(k \geq 3\), it is NP-complete to decide whether a graph is \(k\)-colorable. Because vertex coloring has numerous practical applications such as resource scheduling, compiler register allocation, pattern matching, puzzle solving, and exam timetabling, efficient algorithms to approximate the chromatic number have been developed. In this paper, a need is identified for approximation methods that are suitable for memory-constrained microprocessors with limited instruction sets, such as sensors. A heuristic vertex coloring method is proposed that uses simple operations and limited storage. Computational results are shown to illustrate the effectiveness of the proposed method.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
68W25 Approximation algorithms

Software:

DSATUR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Appel, K.; Haken, W., The solution of the four-color-map problem, Sci. Am., 237, 108-121 (1977)
[2] Arumugam, S.; Premalatha, K.; Bača, M.; Semaničová-Feňovčíková, A., Local antimagic vertex coloring of a graph, Gr. Comb., 33, 2, 275-285 (2017) · Zbl 1368.05124
[3] Barba, L., Cardinal, J., Korman, M., Langerman, S., Van Renssen, A., Roeloffzen, M., Verdonschot, S.: Dynamic graph coloring. In: Workshop on Algorithms and Data Structures, pp. 97-108. Springer (2017) · Zbl 1484.68149
[4] Beigel, R., Eppstein, D.: 3-Coloring in time \(0(1.3446^n)\): a no-MIS algorithm. In: 36th Annual Symposium on Foundations of Computer Science, pp. 444-452. IEEE (1995) · Zbl 0938.68940
[5] Bhattacharya, S., Chakrabarty, D., Henzinger, M., Nanongkai, D.: Dynamic algorithms for graph coloring. In: 29th Annual ACM-SIAM symposium on discrete algorithms, pp. 1-20. Society for Industrial and Applied Mathematics (2018) · Zbl 1402.68139
[6] Bollobás, B., Modern Graph Theory (1998), Berlin: Springer, Berlin · Zbl 0902.05016
[7] Boman, E.G., Bozdağ, D., Catalyurek, U., Gebremedhin, A.H., Manne, F.: A scalable parallel graph coloring algorithm for distributed memory computers. In: European Conference on Parallel Processing, pp. 241-251. Springer (2005) · Zbl 1243.68314
[8] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. The Macmillan Press Ltd. (1976) · Zbl 1226.05083
[9] Bonomo, F.; Chudnovsky, M.; Maceli, P.; Schaudt, O.; Stein, M.; Zhong, M., Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Combinatorica, 38, 4, 779-801 (2018) · Zbl 1413.05101
[10] Brélaz, D., New methods to color the vertices of a graph, Commun. ACM, 22, 4, 251-256 (1979) · Zbl 0394.05022
[11] Burjons, E.; Hromkovič, J.; Královič, R.; Královič, R.; Muñoz, X.; Unger, W., Online graph coloring against a randomized adversary, Int. J. Found. Comput. Sci., 29, 4, 551-569 (2018) · Zbl 1397.68229
[12] Byskov, JM, Enumerating maximal independent sets with applications to graph colouring, Oper. Res. Lett., 32, 6, 547-556 (2004) · Zbl 1052.05055
[13] Chen, L.; Peng, J.; Ralescu, DA, Uncertain vertex coloring problem, Soft Comput., 23, 4, 1337-1346 (2019) · Zbl 1415.05153
[14] Coleman, TF; Moré, JJ, Estimation of sparse Jacobian matrices and graph coloring blems, SIAM J. Numer. Anal., 20, 1, 187-209 (1983) · Zbl 0527.65033
[15] Dao, HT; Kim, S., Vertex graph-coloring-based pilot assignment with location-based channel estimation for massive MIMO systems, IEEE Access, 6, 4599-4607 (2018)
[16] Dharwadker, A., A new proof of the four colour theorem, Can. Math. Soc., 221, 1-34 (2000)
[17] Diks, K.: A fast parallel algorithm for six-colouring of planar graphs. In: International Symposium on Mathematical Foundations of Computer Science, pp. 273-282. Springer (1986) · Zbl 0601.05022
[18] Eppstein, D.: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In: 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 329-337. Society for Industrial and Applied Mathematics (2001) · Zbl 1113.68416
[19] Eppstein, D.: Small maximal independent sets and faster exact graph coloring. In: Workshop on Algorithms and Data Structures, pp. 462-470. Springer (2001) · Zbl 0997.68087
[20] Garey, MR; Johnson, DS, Computers and Intractability (2002), New York: W.H. Freeman and Company, New York
[21] Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: 6th Annual ACM Symposium on Theory of Computing, pp. 47-63. ACM (1974)
[22] Gonthier, G., Formal proof: the four-color theorem, Not. AMS, 55, 11, 1382-1393 (2008) · Zbl 1195.05026
[23] Grech, N., Kastrinis, G., Smaragdakis, Y.: Efficient reflection string analysis via graph coloring. In: 32nd European Conference on Object-Oriented Programming, p. 25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
[24] Grötzsch, H.: Zur Theorie der Diskreten Gebilde. VII. Ein Dreifarbensatz far Dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8, 109-120 (1958/1959)
[25] Grünbaum, B., A problem in graph coloring, Am. Math. Mon., 77, 10, 1088-1092 (1970)
[26] Irving, RW, NP-completeness of a family of graph-colouring problems, Discret. Appl. Math., 5, 1, 111-117 (1983) · Zbl 0504.05032
[27] Janczewski, R.; Kubale, M.; Manuszewski, K.; Piwakowski, K., The smallest hard-to-color graph for algorithm DSATUR, Discret. Math., 236, 1, 151-165 (2001) · Zbl 0999.05038
[28] Jones, MT; Plassmann, PE, A parallel graph coloring heuristic, SIAM J. Sci. Comput., 14, 3, 654-669 (1993) · Zbl 0772.68046
[29] Kučera, L., The greedy coloring is a bad probabilistic algorithm, J. Algorithms, 12, 4, 674-684 (1991) · Zbl 0753.68049
[30] Kuratowski, C., Sur le Probleme des Courbes Gauches en Topologie, Fundamenta Mathematicae, 15, 1, 271-283 (1930) · JFM 56.1141.03
[31] Lawler, EL, A note on the complexity of the chromatic number problem, Inf. Process. Lett., 5, 3, 66-67 (1976) · Zbl 0336.68021
[32] van Lint, J.; Wilson, R., A Course in Combinatorics (2001), Cambridge: Cambridge University Press, Cambridge · Zbl 0980.05001
[33] Lozin, VV; Malyshev, DS, Vertex coloring of graphs with few obstructions, Discret. Appl. Math., 216, 273-280 (2017) · Zbl 1350.05038
[34] Luby, M., A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput., 15, 4, 1036-1053 (1986) · Zbl 0619.68058
[35] Matgraph: Toolbox for Working with Simple, Undirected Graphs. https://www.mathworks.com/matlabcentral/mlc-downloads/downloads/submissions/19218/versions/1/previews/matgraph/html/matgraph/@graph/color.html (2019)
[36] Moalic, L.; Gondran, A., Variations on memetic algorithms for graph coloring problems, J. Heurist., 24, 1, 1-24 (2018)
[37] Mustafa, H.; Schilken, I.; Karasikov, M.; Eickhoff, C.; Rätsch, G.; Kahles, A., Dynamic compression schemes for graph coloring, Bioinformatics, 35, 3, 407-414 (2018)
[38] Mycielski, J., Sur le Coloriage des Graphs, Colloquium Mathematicae, 3, 2, 161-162 (1955) · Zbl 0064.17805
[39] Naor, Joseph, A fast parallel coloring of planar graphs with five colors, Information Processing Letters, 25, 1, 51-53 (1987) · Zbl 0653.68069
[40] Orden, D.; Gimenez-Guzman, J.; Marsa-Maestre, I.; de la Hoz, E., Spectrum graph coloring and applications to Wi-Fi channel assignment, Symmetry, 10, 3, 65 (2018) · Zbl 1392.05106
[41] Petersen, J., Die Theorie der Regulären Graphs, Acta Mathematica, 15, 1, 193-220 (1891) · JFM 23.0115.03
[42] Ramsey, F.: On a problem of formal logic. In: Classic Papers in Combinatorics, pp. 1-24. Springer (2009)
[43] Scheinerman, E.: Coloring Graphs in Matgraph. https://www.mathworks.com/matlabcentral/fileexchange/19218-matgraph/content/matgraph/samples/html/coloring.html (2019)
[44] Şeker, O.; Ekim, T.; Taşkın, ZC, A decomposition approach to solve the selective graph coloring problem in some perfect graph families, Networks, 73, 2, 145-169 (2019)
[45] Silva, E.; Guedes, A.; Todt, E., Independent spanning trees on systems-on-chip hypercubes routing, Int. Conf. Electron. Circuits Syst., 75, 93-96 (2013)
[46] Tarjan, RE; Trojanowski, AE, Finding a maximum independent set, SIAM J. Comput., 6, 3, 537-546 (1977) · Zbl 0357.68035
[47] Welsh, DJ; Powell, MB, An upper bound for the chromatic number of a graph and its application to timetabling problems, Comput. J., 10, 1, 85-86 (1967) · Zbl 0147.15206
[48] Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization, pp. 185-207. Springer (2003) · Zbl 1024.68529
[49] Zhou, Y.; Duval, B.; Hao, JK, Improving probability learning based local search for graph coloring, Appl. Soft Comput., 65, 542-553 (2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.