Abstract
A multicoloring is an assignment where each vertex is assigned not just a single number (a “color”) but a set of numbers. The number of colors assigned to the vertex is specified by the length (or color requirement) parameter of that vertex in the input. As usual, adjacent vertices cannot receive the same color; thus here, the sets of colors they receive must be disjoint. Multicolorings are therefore proper generalizations of ordinary graph colorings. The purpose of this paper is to summarize some of the techniques that have been developed specifically for obtaining good approximate multicolorings in different classes of graphs.
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
Afrati, F., Bampis, E., Fishkin, A., Jansen, K., Kenyon, C.: Scheduling to minimize the average completion time of dedicated tasks. In: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol. 1974, p. 454. Springer, Heidelberg (2000)
Appel, K., Haken, W.: Every planar map is 4-colorable. Contemporary Mathematics 98 (1989)
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41, 153–180 (1994)
Bar-Noy, A., Bellare, M., Halldórsson, M.M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inf. Comp. 140, 183–202 (1998)
Bar-Noy, A., Halldórsson, M.M., Kortsarz, G., Shachnai, H., Salman, R.: Sum multicoloring of graphs. J. Algorithms 37(2), 422–450 (2000)
Bar-Noy, A., Kortsarz, G.: The minimum color-sum of bipartite graphs. J. Algorithms 28, 339–365 (1998)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209, 1–45 (1998)
Buchsbaum, A.L., Karloff, H., Kenyon, C., Reingold, N., Thorup, M.: OPT versus LOAD in Dynamic Storage Allocation. In: STOC 2003 (2003)
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley, Chichester (1998)
Chakrabarti, S., Phillips, C.A., Schulz, A.S., Shmoys, D.B., Stein, C., Wein, J.: Improved Scheduling Problems For Minsum Criteria. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 646–657. Springer, Heidelberg (1996)
Coffman, E.G., Garey, M.R., Johnson, D.S., LaPaugh, A.S.: Scheduling File Transfers. SIAM Journal on Computing 14(3), 744–780 (1985)
Feige, U., Kilian, J.: Zero Knowledge and the Chromatic number. Journal of Computer and System Sciences 57(2), 187–199 (1998)
Garey, M.R., Johnson, D.: Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman, New York (1979)
Gabow, H., Kariv, O.: Algorithms for edge coloring bipartite graphs and multigraphs. SIAM Journal of Computing 11(1) (February 1992)
Gandhi, R., Halldórsson, M.M., Kortsarz, G., Shachnai, H.: Approximating non-preemptive open-shop scheduling and related problems. In: ICALP 2004 (2004)
Gandhi, R., Halldórsson, M.M., Kortsarz, G., Shachnai, H.: Improved Bounds for Sum Multicoloring and Weighted Completion Time of Dependent Jobs (unpublished manuscript) (2004)
Gergov, J.: Algorithms for compile-time memory allocation. In: SODA 1999 (1999)
Giaro, K., Janczewski, R., Kubale, M., Malafiejski, M.: A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 131–145. Springer, Heidelberg (2002)
Goldberg, M.K.: Edge Coloring of Multigraphs: Recoloring Technique. J. Graph Theory 8, 121–137 (1984)
Gonen, M.: Coloring Problems on Interval Graphs and Trees. M.Sc. Thesis, School of Computer Science, The Open Univ., Tel-Aviv (2001)
Graham, R.: Bounds for certain multiprocessing anomalies. Bell System Technical Journal 45, 1563–1581 (1966)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1993)
Holyer, I.: The NP-completeness of Edge-Colouring. SIAM J. Comput. 10(4) (1981)
Hall, L., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to Minimize Average Completion Time: Off-line and On-line Approximation Algorithms. Mathematics of Operations Research 22, 513–544 (1997)
Halldórsson, M.M., Kortsarz, G.: Tools for multicoloring with applications to planar graphs and partial k-trees. J. Algorithms 42(2), 334–366 (2002)
Halldórsson, M.M., Kortsarz, G., Proskurowski, A., Salman, R., Shachnai, H., Telle, J.A.: Multicoloring trees. Inf. Computation 180(2), 113–129 (2003)
Halldórsson, M.M., Kortsarz, G., Shachnai, H.: Sum coloring interval and k-claw free graphs with application to scheduling dependent jobs. Algorithmica 37, 187–209 (2003)
Hoogeveen, H., Schuurman, P., Woeginger, G.: Non-approximability results for scheduling problems with minsum criteria. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 353–366. Springer, Heidelberg (1998)
Jansen, K.: The optimum cost chromatic partition problem. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 25–36. Springer, Heidelberg (1997)
Kim, Y.: Data migration to minimize average completion time. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 97–98 (2003)
Kovács, A.: Sum-multicoloring on paths. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 68–80. Springer, Heidelberg (2004)
Kubale, M.: Preemptive versus non preemptive scheduling of biprocessor tasks on dedicated processors. European J. Operational Research 94, 242–251 (1996)
Kubicka, E.: The chromatic sum of a graph. PhD thesis, Western Michigan University (1989)
Kubicka, E., Kubicki, G., Kountanis, D.: Approximation Algorithms for the Chromatic Sum. In: Proc. First Great Lakes Computer Science Conference. LNCS, vol. 1203, pp. 15–21. Springer, Heidelberg (1989)
Kubicka, E., Schwenk, A.J.: An Introduction to Chromatic Sums. In: Proc. 17th Annual ACM Computer Science Conference, “Computing trends in the 1990’s”, pp. 39–45 (1989)
Lawler, E.L., Lenstra, J.K., Rinnooy-Kan, A.H.G., Shmoys, D.B.: Sequencing and Scheduling: Algorithms and Complexity. In: Graves, S.C., Rinnooy- Kan, A.H.G., Zipkin, P. (eds.) Handbooks in Operations Research and Management Science. Logistics of Production and Inventory, vol. 4, pp. 445–522 (1993)
Malafiejski, M.: The complexity of the chromatic sum problem on cubic planar graphs and regular graphs. Electronic Notes in Discrete Mathematics, vol. 8 (May 2001)
Marx, D.: The complexity of tree multicolorings. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 532–542. Springer, Heidelberg (2002)
Marx, D.: Minimum sum multicoloring on the edges of trees. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 214–226. Springer, Heidelberg (2004)
McDiarmid, C., Reed, B.: Channel assignment and weighted coloring. Networks 36(2), 114–117 (2000)
Motwani, R., Ragavan, R.: Randomized algorithms. Cambridge University Press, Cambridge (1995)
Narayan, L.: Channel assignment and graph multicoloring. In: Handbook of wireless networks and mobile computing. Wiley Series On Parallel And Distributed Computing, pp. 71–94 (2002)
Narayanan, L., Shende, S.: Static frequency assignment in cellular networks. Algorithmica 29(3), 396–401 (2001)
Nicoloso, S., Sarrafzadeh, M., Song, X.: On the sum coloring problem on interval graphs. Algorithmica 23, 109–126 (1999)
Nishizeki, T., Kashiwagi, K.: On the 1.1 edge-coloring of multigraphs. SIAM Journal on Discrete Mathematics 3(3), 391–410 (1990)
Queyranne, M., Sviridenko, M.: Approximation Algorithms for Shop Scheduling Problems with Minsum Objective. Journal of Scheduling 5, 287–305 (2002)
Robertson, N., Sanders, D.P., Seymour, P.D., Thomas, R.: A new proof of the four color theorem. Electron Res. Announc. Amer. Math. Soc. 2, 17–25 (1996)
Szkaliczki, T.: Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is NP-complete. SIAM Journal on Computing 29(1), 274–287 (1999)
Vizing, V.G.: On the estimate of the chromatic class of p-graphs. Diskret. Analiz. 3, 23–30 (1964)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Halldórsson, M.M., Kortsarz, G. (2004). Multicoloring: Problems and Techniques. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds) Mathematical Foundations of Computer Science 2004. MFCS 2004. Lecture Notes in Computer Science, vol 3153. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28629-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-28629-5_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22823-3
Online ISBN: 978-3-540-28629-5
eBook Packages: Springer Book Archive